2 गुणों के साथ Knapsack एल्गोरिदम। इसे 3 डी सरणी में कैसे कार्यान्वित करें?

Question

मुझे 1 से अधिक संपत्ति होने पर knapsack समस्या को समझने में समस्या हो रही है। जब 1 संपत्ति है,

मुझे एक प्रोग्राम लिखना है जो 2 गुणों के साथ knapsack एल्गोरिदम का उपयोग करता है। शिक्षक ने हमें बताया, यह एक 3 डी सरणी में किया जाना है। गलत कार्यान्वयन ओ (2^एन) प्रसंस्करण समय का कारण बन जाएगा। मैं कल्पना नहीं कर सकता कि इस तरह की सरणी कैसी दिखती है।

यहाँ मान लीजिए मेरा इनपुट है:

4 3 4 // number of records below, 1st property of backpack, 2nd property of backpack 
1 1 1 // 1st property, 2nd property, cost 
1 2 2 // 1st property, 2nd property, cost 
2 3 3 // 1st property, 2nd property, cost 
3 4 5 // 1st property, 2nd property, cost 

और उत्पादन है कि ऐसा दिखाई देगा:

4 // the cheapest sum of costs of 2 records 
1 3 // numbers of these 2 records 

उत्पादन का स्पष्टीकरण: 2 रिकॉर्ड के सेट इनपुट के 1'st लाइन में के फिट :

(1) - रिकॉर्ड संख्या 1 और रिकॉर्ड संख्या 3

1 1 1 
+ 2 3 3 
------- 
    3 4 4 

(2) - रिकार्ड संख्या 4

3 4 5 

क्योंकि रिकॉर्ड के 1 सेट सस्ता (4 < 5) है, हम इसे चुना है। न केवल मुझे यह पता लगाना होगा कि रिकॉर्ड्स का ऐसा सेट मौजूद है या नहीं, मुझे उन अभिलेखों को भी ढूंढना होगा जिन्हें मैंने समझाया है।

लेकिन अभी के लिए, मुझे केवल समझने की जरूरत है, 3 डी सरणी कैसा दिखता है। क्या आप में से कुछ मेरी मदद कर सकते हैं और दिखा सकते हैं, परत से परत, बस मेरी छवि में, यह कैसा दिखता है? धन्यवाद।

Answer 1

आप कुछ असंभव करने की कोशिश कर रहे हैं - यह आपकी समस्या है।

जब आप आयामों की संख्या में जोड़ रहे हैं, तो आपके आइटम अतिरिक्त गुण प्राप्त कर रहे हैं। तो, एक बाएं, एक तालिका के कॉलम पक्ष (prop1) के बजाय, आपके पास आयताकार पक्ष (prop1 x prop2) या ब्लॉक (prop1 x prop2 x prop3) और इसी तरह ब्लॉक करें। लेकिन मौजूदा बाधाएं, जो तालिका के ऊपरी, पंक्ति पक्ष को परिभाषित करती हैं, में समान आयाम होना चाहिए। न केवल एक आयाम!। तो, आप कभी दो-संपत्ति समस्या को 3-आयामी ब्लॉक में रखने में सक्षम होंगे, आपको इसके बजाय 4 डी ब्लॉक की आवश्यकता होगी। 3 गुणों के लिए 6 डी ब्लॉक और इतने पर।

Answer 2

2-बाधा समस्या को हल करने के लिए गतिशील प्रोग्रामिंग के साथ 1-बाधा नॅपैकैक समस्या को हल करने के लिए एल्गोरिदम से कनवर्ट करने के लिए बहुत आसान है। किसी के लिए एक 3 डी छवि खींचने के लिए जो आपको दिखाता है कि वहां क्या हो रहा है, मुझे कल्पना है कि कुछ मुश्किल है। दूसरी तरफ, एल्गोरिदम काफी आसान है:

मुझे लगता है कि आप एक सटीक फिट समाधान चाहते हैं, और आप लागत को कम करना चाहते हैं, मूल्य को अधिकतम नहीं (जो मैंने आपके उदाहरण से प्राप्त किया है)। मैंने पहले इनमें से कोई भी बदलाव नहीं किया है, इसलिए मैं गारंटी नहीं दे सकता कि कोई त्रुटि नहीं है।

1-बाधा

1-बाधा नेप्सेक समस्या (item x weight) है प्रत्येक स्थिति में मूल्य के भंडारण के लिए मैट्रिक्स।बस है

// WL = backpack weight limit 
A[0, 0] = 0 
for w = 1, 2, ..., WL // weight 
    A[0, w] = INFINITY 
for i = 1, 2, ..., n // items 
    for w = 0, 1, ..., WL // weight 
    // wi and ci are the weight and cost of the item respectively 
    // A[i-1, w-wi] + ci = 0 when wi > w 
    A[i, w] = min(A[i-1, w], A[i-1, w-wi] + ci) 

2-बाधा

अब यह विस्तार करने के लिए एक और बाधा में शामिल हैं::

एल्गोरिथ्म मूल रूप से है

(मान लीजिए कि size अन्य बाधा है करते हैं) मैट्रिक्स (item x weight x size) होगा।

// WL = backpack weight limit 
// SL = backpack size limit 
for w = 0, 1, ..., WL // weight 
    for s = 0, 1, ..., SL // size 
    A[0, w, s] = INFINITY 
A[0, 0, 0] = 0 
for i = 1, 2, ..., n // items 
    for w = 0, 1, ..., WL // weight 
    for s = 0, 1, ..., SL // size 
     // wi, si and ci are the weight, size and cost of the item respectively 
     // A[i-1, w-wi, s-si] + ci = 0 when wi > w or si > s 
     A[i, w, s] = min(A[i-1, w, s], A[i-1, w-wi, s-si] + ci)