في الحقيبة
الوزن
أفضل الممكن

    الأغراض

      مزيد عن مسألة حقيبة الظهر

      مسألة حقيبة الظهر

      لا يمكنك حمل إلا وزن محدود، ولكل غرض وزن وقيمة. أي الأغراض تأخذ لتحمل أكبر قيمة؟ تجربة كل التركيبات تضاعف العمل مع كل غرض جديد. أما جدول صفوفه الأغراض وأعمدته السعات فيجد أفضل حقيبة خلية بعد خلية. اضغط على غرض لوضعه في الحقيبة، واضغط عليه مرة أخرى (في الحقيبة أو على الرف) لإخراجه. تمتلئ الحقيبة بحسب الوزن، وتعرض البطاقات الدولارات التي عبأتها مقارنةً بأفضل ما يمكن. اضغط «أفضل تعبئة» لترى أفضل حقيبة. من اللوحة، غيّر كيلوغرامات الأغراض ودولاراتها، وأضف أغراضًا أو احذفها، واضبط سعة الحقيبة. تُظهر طريقة عرض «الجدول» كيف تجد البرمجة الديناميكية أفضل حقيبة: اضغط «تشغيل» لتشاهد الجدول يمتلئ، أو «خطوة» و«رجوع» للتحرك خطوة واحدة في كل مرة، واسحب شريط الخطوات للانتقال إلى أي موضع. كل صف يضيف غرضًا واحدًا، وكل عمود سعة بالكيلوغرام، وكل خلية تحمل أكبر عدد من الدولارات يتسع. عند تحديد الجدول، تتقدم مفاتيح الأسهم خطوة خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

      كيف يعمل

      1. انقر على صناديق الأغراض لوضعها في الحقيبة، وشاهدها تمتلئ حسب الوزن بالكيلوغرام.
      2. حاول الوصول إلى أفضل قيمة ممكنة بالدولار، أو اضغط «أفضل تعبئة» لرؤية أفضل حقيبة.
      3. افتح عرض «الجدول» واضغط تشغيل لتشاهد كل خلية وهي تختار بين وضع الغرض وتركه.

      كيف يعمل الجدول

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

      تتبّع الأغراض عكسيًا

      الخلية السفلية اليمنى هي أفضل قيمة. لإيجاد الأغراض، ابدأ منها وقارنها بالخلية التي فوقها: إن كانت مساوية لها فالغرض الأخير لم يكن لازمًا؛ وإن كانت أكبر فالغرض في الحقيبة، فاطرح وزنه وانتقل إلى ذلك العمود. اصعد صفًا واحدًا في كل مرة حتى الصف الأول. يعرض التطبيق هذا التتبع العكسي باللون البرتقالي ويسرد الأغراض المعبأة تحت الجدول.

      الأسئلة المتداولة

      ماذا يعني 0/1 في مسألة حقيبة الظهر 0/1؟

      كل غرض يوضع مرة واحدة أو لا يوضع أبدًا، لا يوضع جزء منه ولا يوضع مرتين. لو أمكن تقسيم الأغراض، مثل حبات الأرز، لكان وضع الأفضل قيمة لكل وحدة وزن أولًا هو الحل الأمثل؛ وهذه هي مسألة حقيبة الظهر الكسرية.

      لماذا لا نضع الغرض ذا أفضل قيمة لكل وحدة وزن أولًا؟

      لأن الأغراض الكاملة قد تترك فراغات. مع سعة 7 وأغراض أوزانها 1 و3 و4 و5 وقيمها 1 و4 و5 و7، يكون الغرض ذو أفضل قيمة لكل وحدة وزن هو الغرض الذي وزنه 5، ولا يترك مكانًا إلا للغرض الذي وزنه 1، فيكون المجموع 8. أما الغرضان اللذان وزنهما 3 و4 فقيمتهما معًا 9.

      ما سرعة خوارزمية حقيبة الظهر؟

      في الجدول (عدد الأغراض + 1) مضروبًا في (السعة + 1) خلية، تُملأ كل منها في خطوة واحدة. هذا سريع للسعات الصغيرة، لكن السعة قد تكون عددًا ضخمًا، لذا فالمسألة NP-صعبة في العموم؛ وتُسمى طريقة الجدول شبه متعددة الحدود.

      هل يمكن وضع الغرض نفسه مرتين؟

      ليس هنا. في مسألة حقيبة الظهر غير المحدودة يمكن أخذ كل غرض أي عدد من المرات؛ وعندها يقرأ الجدول الخلية التي على اليسار في الصف نفسه بدلًا من الصف الذي فوقها، كما في تطبيق صرف العملات.

      هل يُرسل أي شيء إلى أي مكان؟

      لا. كل شيء يُحسب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.

      هل أنت مستعد لتجربتها؟

      افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

      الانتقال إلى المحرر