إعداد مشكلة Quapsack. تريد: قائمة بجميع الحزم الممكنة

Question

بدلاً من تحسين أي شيء ، أريد أن أدرج كل ما هو ممكن - بما في ذلك عبوات "غير مكتملة" من The Knapsack. بالطبع ، يمكنني أن أحلق جميع المجموعات الفرعية من مجموعة الكائنات واختيار تلك التي ترضي قيود الوزن (يمكن تحسينها عن طريق وضع حد أعلى على حجم المجموعات الفرعية للنظر من خلاله) ، لكنني أحب شيئًا أكثر فعالة.

شكرًا.

Answer 1

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

إذا تمكنا من حزم أكثر من عنصر واحد من نوع معين ، فاستبدل أقل من أقل من أو يساوي.

إذا كان لدينا كائنات متعددة من نفس الوزن ، نحتاج إلى الفرز أولاً حسب الوزن ، ثم ببعض الترتيب التعسفي ، واستخدام ذلك.

 PackKnapsack(knapsack, objects)
   add knapsack to list
   if objects is empty return
   if smallest object does not fit return
   for each object in order from smallest to largest
      if currentobject does not fit
         break
      PackKnapsack(knapsack + currentObject, objects heavier than current object)