2 knapsacks भरने का इष्टतम तरीका?

Question

गतिशील प्रोग्रामिंग एल्गोरिदम एक नापसैक भरने के लिए अच्छी तरह से एक knapsack भरने के लिए अच्छी तरह से काम करता है। लेकिन क्या एक कुशल ज्ञात एल्गोरिदम है जो 2 knapsacks को बेहतर रूप से भर देगा (क्षमता असमान हो सकती है)?

मैंने निम्नलिखित दो दृष्टिकोणों का प्रयास किया है और उनमें से कोई भी सही नहीं है।

1. पहले एक knapsack भरने के लिए मूल डीपी एल्गोरिदम का उपयोग करके पहले knapsack भरें और फिर अन्य knapsack भरें।
2. पहले आकार W1 + W2 का एक knapsack भरें और फिर समाधान को दो समाधानों में विभाजित करें (जहां W1 और W2 दो knapsacks की क्षमताओं हैं)।

समस्या बयान (देखें भी विकिपीडिया पर Knapsack Problem):

1. हम (प्रत्येक आइटम एक वजन और एक मूल्य है) इतनी के रूप में मान बढ़ाने के लिए आइटम का एक समूह के साथ नैपसैक भरना चूंकि हम कुल वजन को नापसैक आकार से कम या उसके बराबर रखते हुए आइटम से प्राप्त कर सकते हैं।

2. हम एक आइटम का कई बार उपयोग नहीं कर सकते हैं।

3. हम किसी आइटम का एक हिस्सा उपयोग नहीं कर सकते हैं। हम किसी वस्तु का अंश नहीं ले सकते हैं। (प्रत्येक आइटम या तो पूरी तरह से शामिल किया जाना चाहिए या नहीं)।

Answer 1

मुझे लगता है कि n आइटमों में से प्रत्येक का उपयोग केवल एक बार किया जा सकता है, और आपको अपने लाभ को अधिकतम करना होगा।

मूल नैपसैक dp[i] = best profit you can obtain for weight i

for i = 1 to n do 
    for w = maxW down to a[i].weight do 
    if dp[w] < dp[w - a[i].weight] + a[i].gain 
     dp[w] = dp[w - a[i].weight] + a[i].gain 

है अब, के बाद से हम दो knapsacks है, हम उपयोग कर सकते हैं dp[i, j] = best profit you can obtain for weight i in knapsack 1 and j in knapsack 2

for i = 1 to n do 
    for w1 = maxW1 down to a[i].weight do 
    for w2 = maxW2 down to a[i].weight do 
     dp[w1, w2] = max 
        { 
         dp[w1, w2], <- we already have the best choice for this pair 
         dp[w1 - a[i].weight, w2] + a[i].gain <- put in knapsack 1 
         dp[w1, w2 - a[i].weight] + a[i].gain <- put in knapsack 2 
        } 

समय जटिलता O(n * maxW1 * maxW2) है, जहां maxW अधिकतम वजन नैपसैक ले जा सकता है। ध्यान दें कि यदि क्षमताएं बड़ी हैं तो यह बहुत प्रभावी नहीं है।

Answer 2

मूल डीपी आपको डीपी सरणी में चिह्नित करता है जो कि आप knapsack में प्राप्त कर सकते हैं, और परिणाम तत्वों पर विचार करके अद्यतन किए जाते हैं।
2 knapsacks आप 2-आयामी गतिशील सरणी का उपयोग कर सकते हैं, इसलिए डी पी [मैं] [जे] = 1 के मामले जब आप दूसरे नैपसैक वजन मैं पहले और वजन j को डाल सकते हैं। अद्यतन मूल डीपी मामले के समान है।

Answer 3

पुनरावर्ती सूत्र किसी को भी देख रहा है है:

को देखते हुए एन आइटम, इस तरह है कि आइटम मैं वजन वाई और मूल्य अनुकरणीय है। डब्ल्यू 1 और डब्ल्यू 2 की दो knapsacks havk क्षमताओं।

हर 0 < के लिए = मैं < = n, 0 < = एक < = W1, 0 < = b < = डब्ल्यू 2, एम [मैं, ए, बी] अधिक से अधिक मूल्य को दर्शाते हैं।

के लिए

एक < 0 या ख < 0 - एम [मैं, ए, बी] = -∞ के लिए मैं = 0, या ए, बी = 0 - एम [मैं, ए, बी] = 0

सूत्र: एम [i, ए, बी] = अधिकतम {एम [i-1, ए, बी], एम [i-1, ए-वाई, बी] + पीआई, एम [i-1, ए, बी-वाईआई] + पीआई}

मेरे आइटम के साथ समस्या का हर समाधान या तो मेरे पास knapsack 1 में, knapsack 2 में, या उनमें से कोई भी नहीं है।