حل تشریحی سوال شماره 42 دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

فرض کنید مسئله ای به نام تقسیم مجموعه با تفاوت کمینه (Minimum Difference Partitioning) داریم به شما یک مجموعه از n عدد صحیح مثبت داده شده است. هدف این است که مجموعه را به دو زیر مجموعه تقسیم کنید به طوری که تفاوت مجموع عناصر دو زیر مجموعه کمینه باشد. برای این مسئله میخواهیم از رویکرد شاخه و حد (Branch and Bound) استفاده کنیم. کدام یک از روش‌های زیر بهینه‌ترین راه برای محاسبه حد پایین (Lower Bound) در هر گره است تا شاخه های کم بازده به سرعت هرس شوند؟