حقيبة الظهر

التعليمات

مهمتك هي تحديد العناصر التي ينبغي أخذها بحيث تصبح القيمة الإجمالية لاختيارها هي الأكبر، مع مراعاة سعة الحقيبة على الحمل.

ستُمثَّل العناصر كمصفوفة من العناصر. سيكون لكل عنصر وزن وقيمة. ستكون جميع القيم المعطاة موجبة قطعًا. لا تستطيع Lhakpa أخذ أكثر من واحدة من كل عنصر.

على سبيل المثال:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

في المثال أعلاه، وزن العنصر الأول 5 وقيمته 10، ووزن العنصر الثاني 4 وقيمته 40، وهكذا. في هذا المثال، ينبغي لـ Lhakpa أن تأخذ العنصرين الثاني والرابع لتعظيم قيمتها، وهي في هذه الحالة 90. لا يمكنها الحصول على أكثر من 90 لأن حقيبة الظهر لديها حد للوزن مقداره 10.

ملاحظات خاصة بـ WebAssembly

تُمرَّر العناصر عبر الذاكرة الخطية، بحيث يكون العنصر الأول عند الإزاحة 0. يُمثَّل كل عنصر كزوج من الأعداد الصحيحة ذات 32 بت. العدد الأول في الزوج هو الوزن، والثاني هو القيمة.

على سبيل المثال، لنأخذ قائمة من عنصرين، وزن الأول weight=1, value=2 والثاني weight=5, value=8. وهكذا ستبدو القائمة في الذاكرة:

| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
| - item 1 weight - | -- item 1 value - | - item 2 weight - | -- item 2 value - |
|0x01,0x00,0x00,0x00|0x02,0x00,0x00,0x00|0x05,0x00,0x00,0x00|0x08,0x00,0x00,0x00|

إذا أردت ذلك، يمكنك الكتابة فوق عناوين الذاكرة الخطية المستخدمة للمدخلات.

---

المصدر

ويكيبيديا