التعبئة خوارزمية نوع من ...

Question

بالنظر إلى مجموعة من العناصر ، كل منها يحتوي على value و cost, ما هو أفضل خوارزمية تحديد العناصر المطلوبة للوصول إلى الحد الأدنى من قيمة بأقل تكلفة ؟ على سبيل المثال:

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

علما بأن القيمة الإجمالية:نسبة التكلفة في النهاية هو غير ذي صلة (A + A سوف تعطيك أفضل قيمة مقابل المال ، ولكن A + B + B هو خيار أرخص الذي يضرب قيمة الحد الأدنى).

Answer 1

هذا هو حقيبة المشكلة.(هذا هو إصدار قرار من هذه المشكلة هو نفس إصدار قرار حقيبة المشكلة, على الرغم من التحسين نسخة من حقيبة المشكلة عادة ما جاء بشكل مختلف.) فمن NP-hard (يعني لا خوارزمية المعروف أن هو متعدد الحدود في "حجم" -- عدد البتات في المدخلات).ولكن إذا كان لديك أرقام صغيرة (أكبر "قيمة" في المدخلات ، يقول ؛ تكاليف لا يهم) ، ثم هناك بسيطة البرمجة الديناميكية الحل.

اسمحوا أفضل[v] أن تكلفة الحد الأدنى للحصول على قيمة (بالضبط) ضدثم يمكنك حساب القيم أفضل[] لجميع الخامس قبل (تهيئة جميع أفضل[v] إلى ما لا نهاية،):

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

ثم ننظر في أفضل[v] من أجل قيم تصل إلى الحد الأدنى تريد بالإضافة إلى أكبر قيمة ؛ أصغر من تلك التي سوف تعطيك تكلفة.

إذا كنت ترغب في العناصر الفعلية (وليس فقط الحد الأدنى من التكلفة) ، يمكنك إما الحفاظ على بعض البيانات الإضافية ، أو مجرد إلقاء نظرة من خلال مجموعة من أفضل[]s و نستنتج من ذلك.

Answer 2

هذه المشكلة كما هو معروف صحيح البرمجة الخطية.إنه NP-hard.ومع ذلك ، بالنسبة المشاكل الصغيرة مثل المثال الخاص بك, انها تافهة لجعل سريع بضعة أسطر من التعليمات البرمجية ببساطة القوة الغاشمة جميع انخفاض مجموعات من شراء الخيارات.

NP-harddoesn لا يعني المستحيل أو مكلفة حتى يعني مشكلتك يصبح بسرعة أبطأ إلى حل مع نطاق واسع من المشاكل.في حالة الخاص بك مع فقط ثلاثة بنود ، يمكنك حل هذا في مجرد ميكروثانية.

بالضبط السؤال ما هو أفضل خوارزمية عامة..هناك بأكمله الكتب المدرسية على ذلك.بداية جيدة هو القديمة الجيدة في ويكيبيديا.

Answer 3

تحرير هذا الجواب هو حجب على حساب من يجري في الواقع غير صحيح.بعد المشورة في هذا سوف يسبب لك الضرر.

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

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

Amenddum هذا في الواقع قد يكون أيضا NP-complete, ولكن أنا لست متأكدا حتى الآن.على أي حال بالنسبة لجميع الأغراض العملية هذا الاختلاف ينبغي أن يكون أسرع بكثير من السذاجة الحل.