كيفية إدراك خوارزمية مقابلة في منتصف الأوسط لمدة 0-1

Question

أنا الآن أدرس مشكلة بعناية (KP)، والعثور على خوارزمية Meet-met-of move الموصوفة في wikipedia غير واضح قليلا، وكيفية إدراكها في الوقت النظري تعقيد $ O ^ * (2 ^ {n / 2}) $ ؟ أستطيع أن أفهم خوارزمية لمشكلة المجموع الفرعي (SSP) وهي مثيل معين من 0-1 KP، ولكن بالنسبة للمشكلة المعممة قد تكون هناك خطأ في الخطوة:

giveacodicetagpre.

كما أفهم، هذا هو البحث (على سبيل المثال. قم بالبحث الثنائي) على الأوزان المجمعة لجميع مجموعات فرعية من B، والتي تأخذ وقت اللوغاريتم الوقت لكل بحث. ولكن بعد معرفة فرع فرعي قد جمعت الوزن أقل من ث، كيف تجد واحدة من أعظم قيمة؟ إذا كان البحث حول قيم المجموعات الفرعية مع الوزن $ O ^ * (2 ^ {n / 2}) $ ، ولكن شيء مثل $ o ^ * (2 ^ n) $ .

حتى لو كان يبدأ من العثور على مجموعة فرعية من أعظم قيمة (من السهل على الطاولة) أولا دون انقباض على الوزن المشترك، بعد ذلك، من المحتمل أن يتحول التحقق من الوزن، وبالتالي هناك حاجة إلى مزيد من الاختبارات لمكافحة فرعية أخرى، منها يبدو الرقم مرتبط بحجم الجدول خطيا مرة أخرى.

الآن أستطيع أن أفترض فقط القيمة الإجمالية والوزن المشترك ملوطا إيجابيا بقوة، بحيث بعد العثور على مجموعة فرعية ذات وزن مسموح به الحد الأقصى، فإنه يستغرق البحث فقط في البحث حول هذه المجموعة الفرعية للضبط واحد من أعظم القيمة. لكنني لست راضيا عن هذا التفسير. لذلك أي شخص لديه أفكار أفضل حول هذه المشكلة؟

ps: لقد قرأت الورقة الأصلية بواسطة Horowitz و Ellis و Sahni، Sartaj، لكنني وجدت المشكلة المحددة هناك مشكلة في القرار بدلا من مشكلة التحسين المشترك. ربما يمكن لشخص ما تقديم الأفكار في هذا الاتجاه.

Answer 1

أولا، قبل الأوزان من كل مجموعة فرعية من $ B $ .

فرزها بالوزن ووضع الأوزان والجهاز الفرعي في صفائف متوازية بحيث $ w [i]= الوزن $ و $ الأفضل [i] $ هو الفهرس $ J $ من مجموعة قيمة أكبر مثل $ J <= i $ .يمكنك القيام بذلك باستخدام فحص واحد من $ i= 0 $ التصاعدي، أو تذكر أكبر قيمة شوهدت حتى الآن في كل خطوة.

الآن، للبحث $ B $ ، يمكنك إجراء بحث ثنائي في $ W $ للعثورالحد الأقصى للوزن المسموح به، والحصول على أفضل مجموعة من نفس الفهرس في $ best $