एक अतिरिक्त संपत्ति के साथ Knapsack एल्गोरिदम

Question

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

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

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

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

Answer 2

कहें कि आप तीन आयाम तालिका का उपयोग कर रहे हैं: A[x][y][z]=k, x: राशि पहली संपत्ति; y: दूसरी संपत्ति राशि; z: कुल तीसरी संपत्ति; के: न्यूनतम लागत (अधिकतम इनाम, जिसे मैं इनाम का उपयोग करना पसंद करता हूं)

तो आप आइटमों पर फिर से प्रयास करते हैं। वर्तमान आइटम कहें (पी 1, पी 2, पी 3, इनाम) (इनाम = - लागत)।प्रत्येक (x,y,z,k) के लिए, आपकी नई जानकारी सूत्र:

A[x+p1][y+p2][z+p3] = max(A[x+p1][y+p2][z+p3], A[x+p1][y+p2][z+p3] + reward) 

तो आरएचएस पर 1 अवधि में अधिक है, स्लॉट A[x+p1][y+p2][z+p3] पर, नेप्सेक के विन्यास अभी भी बनी हुई है, अन्यथा, आप A[x+p1][y+p2][z+p3] और वर्तमान आइटम के द्वारा knapsack को अद्यतन करते हैं।

आशा है कि यह कट चीजों को स्पष्ट करें।