افراز لیست به دو قسمت

[sataho]

سلام
اگه بخوایم یه لیست از n تا عدد صحیح مثبت را به دو تا لیست با n/2 عدد تقسیم کنیم . به قسمی که اختلاف میان حاصل جمع دو لیست حد اقل باشه . چه الگوریتمی پیشنهاد می کنین ؟

[qwerty11]

سلام،
چون به نظر تمرین دانشجویی میاد یه کوچولو (البته اگر دقت کنید خیلی بزرگه) راهنمایی میکنم :

dynamic programming

فرض کنید s مجموع تمام اعداد لیست باشه، a[i][j] I مساوی با یک هستش اگه زیرمجموعه ای از i تا عنصر اول وجود داشته باشه که مجموع عناصرش برابر j باشه، در غیر این صورت a[i][j] I مساوی صفر هستش.

و ...