مجموع زیرمجموعه (طرح تقریب کاملاً چندجمله‌ای)
بزرگ‌ترین جمع زیرمجموعه‌ای را که از t بیشتر نشود تقریب می‌زند؛ با هرس جمع‌های نزدیک به هم، فهرست کوتاه می‌ماند و جواب حداکثر (1 + ε) برابر کمتر از بهینه است.
مجموع زیرمجموعه: از مجموعه‌ی S، زیرمجموعه‌ای با بزرگ‌ترین جمعی که از t بیشتر نشود. حل دقیق NP-سخت است: فهرست همه‌ی جمع‌های ممکن می‌تواند 2ⁿ عضو داشته باشد.
- زمان:
O(n² ln t / ε) - حافظه:
O(n ln t / ε) - CLRS، بخش ۳۵.۵
S = {104, 102, 201, 101}، t = 308 و ε = 0.4؛ جواب تقریبی ۳۰۲ و جواب بهینه ۳۰۷ (= ۱۰۴ + ۱۰۲ + ۱۰۱)، در محدوده‌ی ۴۰٪.
def approx_subset_sum(items, target):eps = 0.4delta = eps / (2 * len(items))sums = [0]rows = []for x in items:merged = sorted(set(sums + [s + x for s in sums]))# Trim: drop a sum that is within a factor (1 + delta) of the last one kept.kept = [merged[0]]for s in merged[1:]:if s > kept[-1] * (1 + delta):kept.append(s)sums = [s for s in kept if s <= target]rows.append([x] + sums)return max(sums)
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
items list
Call stack
- approx_subset_sum()خط 1
توضیح
ایده
مجموع زیرمجموعه: از مجموعه‌ی S، زیرمجموعه‌ای با بزرگ‌ترین جمعی که از t بیشتر نشود. حل دقیق NP-سخت است: فهرست همه‌ی جمع‌های ممکن می‌تواند 2ⁿ عضو داشته باشد.
هرس کردن
اگر دو جمع خیلی نزدیک‌اند (یکی حداکثر (1 + δ) برابر دیگری)، نگه داشتن یکی کافی است؛ خطای هر هرس کوچک است و روی هم حداکثر (1 + ε) می‌شود. با δ = ε / 2n فهرست همیشه کوتاه می‌ماند.
نتیجه یک طرح تقریب کاملاً چندجمله‌ای (FPTAS) است: زمان بر حسب n و 1/ε چندجمله‌ای است و با ε کوچک‌تر، جواب دقیق‌تر ولی کندتر.
در trace به چه چیزی نگاه کنی
- هر سطر جدول عضو تازه و فهرست جمع‌های نگه‌داشته بعد از هرس است. در ورودی «مثال به سبک کتاب» ببین چرا ۳۰۷ از دست می‌رود.