مسئله تقسیم‌بندی

مثال‌ها

با داشتن مجموعه
{S = {3,1,1,2,2,1 یک راه‌حل ممکن برای مسئله تقسیم‌بندی زیرمجموعه‌های {S₁ = {1,1,1,2 و {S₂ = {2,3 می‌باشد که در هر دو حاصل جمع اعضا 5 است.
توجه کنید که این راه‌حل یکتا نیست زیرا {S₁ = {3,1,1 و {S₂ = {2,2,1 راه‌حل دیگری برای این مسئله می‌باشد.

الگوریتم شبهه چندجمله‌ای

الگوریتم به این نحو کار می‌کند که یک جدول با  سطر و n ستون حاوی مقادیر بازگشتی می‌سازد. هنگامی که کل جدول ساخته شد، مقدار ( p (, n را در خروجی برمی‌گرداند. در شکل زیر یک نمونه از جدول P را ملاحظه می‌نمایید. در صورتی که مقدار یک خانه از جدول به مقدار خانه دیگری وابسته باشد، یک پیکان از خانه دوم به اول در شکل رسم شده‌است.
   INPUT:  A list of integers S
   OUTPUT: True if S can be partitioned into two subsets that have equal sum
1 function find_partition( S ):
2     n ← |S|
3     N ← sum(S)
4     P ← empty boolean table of size ( +  1) by (n + 1)
5     initialize top row (P(0,x)) of P to True
6     initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
7     for i from 1 to 
8          for j from 1 to n
9          P(i, j) ← P(i, j-1) or P(i-S[j-1], j-1)
10    return P(, n)

مثال

در شکل زیر جدول P را برای مجموعهٔ {S = {3,1,1,2,2,1 مشاهده می‌کنید.

زمان اجرا

پیچیدگی زمانی این الگوریتم  می‌باشد که  تعداد اعضای مجموعه در ورودی است و  حاصل‌جمع این عضوها می‌باشد.

الگوریتم حریصانه

در این الگوریتم که روی اعضای مجموعه که به صورت نزولی مرتب شده‌اند اجرا می‌شود، هر عضو داخل زیرمجموعه‌ای می‌رود که مجموع اعضایش کوچکتر است. این الگوریتم هنگامی که مقادیر اعضا برابر یا کمتر از تعداد آن‌ها باشد در مجموعه باشد، به خوبی کار می‌کند. زمان اجرای این الگوریتم  است.
بدیهی است که این الگوریتم ممکن است درست عمل نکند. برای مثال برای مجموعه {S = {5, 5, 4, 3, 3 الگوریتم حریصانه زیرمجموعه‌های {S₁ = {5, 4 و {S₂ = {5, 3, 3 را انتخاب می‌کند در حالی که پاسخ صحیح {S₁ = {5, 5 و {S₁ = {4, 4, 4 است.
این روش جوابی به اندازه ۴/۳ برابر جواب بهینه را می‌دهد. یعنی اگر این الگوریتم دو جواب  و  را بدهد، آنگاه:
در زیر شبه‌کد الگوریتم حریصانه آورده شده‌است.
   INPUT:  A list of integers S
   OUTPUT: An attempt at a partition of S into two sets of equal sum
1 function find_partition( S ):
2     A ← {}
3     B ← {}
4     sort S in descending order
5     for i in S:
6         if sum(A) <sum(B)
7              add element i to set A
8         else
9              add element i to set B
10     return {A, B}

الگوریتم تفاضلی

یکی دیگر از الگوریتم‌های اکتشافی الگوریتم تفاضلی است که در هر مرحله دو عدد از مجموعه انتخاب می‌کند و آن‌ها را با تفاضلشان جایگزین می‌کند. این در واقع به معنای قرار دادن این دو عدد در دو زیرمجموعه مجزا می‌باشد بدون اینکه مشخص شود هرکدام از آن‌ها داخل کدام زیرمجموعه می‌شوند. این الگوریتم بهتر از الگوریتم حریصانه عمل می‌کند اما همچنان برای نمونه‌هایی از مسئله که در آن تعداد اعضای مجموعه به صورت نمایی هستند جواب خوبی نمی‌دهد.

نمونه‌های سخت

مجموعه‌های که یک یا هیچ تقسیم‌بندی برای آن‌ها وجود ندارد، نسبت به اندازه ورودی‌شان مشکل‌ترین هستند. هنگامی که مقادیر اعضا نسبت به اندازه مجموعه کوچک است، احتمال تقسیم‌بندی بهینه بیشتر است. پس می‌گوییم مسئله دستخوش تغییر فاز شده‌است بدین معنا که برای بعضی از مجموعه‌ها محتمل و برای برخی دیگر غیر محتمل است.
اگر m را تعداد بیت‌های مورد نیاز برای نشان دادن اعداد داخل مجموعه باشد و n اندازه مجموعه باشد، بنابراین شرط  به جواب‌های زیادی منتهی می‌شود در حالی که  دارای جواب‌های کمتر و در برخی موارد بدون جواب است. در نتیجه هرچه n و m بیشتر می‌شوند، احتمال تقسیم‌بندی بهینه بین ۰ و ۱ در نوسان است.

مسئله تقسیم‌بندی Kتایی

حالت دیگری از مسئله تقسیم‌بندی به نام تقسیم‌بندی ۳تایی وجود دارد که مسئله تقسیم مجموعه S به S|/3| زیرمجموعه با مجموع‌های برابر است. این مسئله با مسئله تقسیم‌بندی متفاوت است و هیچ راه‌حل شبه چندجمله‌ای برای آن وجود ندارد مگر P=NP.