حل تشریحی سوال شماره 6 ساختمان داده

مسئله جمع زیر مجموعه بدین شکل تعریف می‌شود: یک مجموعه از اعداد مثبت $S=\left\{a_1\dots a_n\right\}$ به همراه عدد W داده شده است. آیا زیر مجموعه‌ای از S پیدا می‌شود که جمع اعضای آن W شود؟

برای حل این مسئله به‌روش برنامه‌ریزی پویا یک آرایه دو بعدی $X\left[\mathrm{1..}n,\mathrm{0..}W\right]$ تعریف می‌کنیم که $X\left[i,j\right]$ برابر True است. اگر زیر مجموعه‌ای از $S=\left\{a_1\dots a_i\right\}$ وجود داشته باشد که جمع اعضای آن j شود، در این خصوص کدام رابطه درست است؟