जबकि मानक knapsack समस्या को गतिशील प्रोग्रामिंग द्वारा हल किया जा सकता है, मैं अपनी अवधारणा को दूर करने के लिए समस्या को थोड़ा मोड़ने की कोशिश कर रहा हूं, हालांकि मुझे लगता है कि मैंने इसे सोचा जितना कठिन हो सकता है।पारस्परिक रूप से अनन्य वस्तुओं के साथ नापसैक
मूल नेप्सेक समस्या है कि आकार W साथ नेप्सेक, और आइटम जो वजन w[i] और एक मूल्य v[i] है की एक सूची दी गई है, आइटम जो उच्चतम कुल मूल्य के साथ नेप्सेक में फिट कर सकते हैं के सबसेट पाते हैं।
मेरी समझ के लिए, यह गतिशील प्रोग्रामिंग के साथ O(Wn) द्वारा किया जा सकता है, जहां n आइटम की संख्या है।
अब अगर मैं m constrains जोड़ने के लिए, उनमें से प्रत्येक केवल आपसी विशेष रूप से उठाया जा सकता है जो मदों की एक जोड़ी है की कोशिश (यानी अगर कोई आइटम एक और आइटम बी के एक विवश मौजूद हैं, तो मैं केवल ले जा सकते हैं उनमें से एक या दोनों नहीं)
ऐसी बाधाओं के तहत, क्या इस समस्या को अभी भी O(Wn) में गतिशील प्रोग्रामिंग द्वारा हल किया जा सकता है?
अभी भी पचता है लेकिन मेरे लिए बहुत मान्य लगता है ... बस मेरे दिमाग को साफ़ करने के लिए, इसका मतलब यह है कि यदि प्रत्येक बाधा एक जोड़ी नहीं है, लेकिन वस्तुओं का एक सेट है, जिसमें प्रत्येक आइटम पारस्परिक रूप से अनन्य होना चाहिए, जो अभी भी हो सकता है उसी एल्गोरिदम का उपयोग किया जिसमें ओ (डब्ल्यूएन) समय है? – shole
@ शोल जब तक बाधाएं ओवरलैप नहीं हो रही हैं (कोई भी एक से अधिक बाधाओं में मौजूद नहीं है), इस दृष्टिकोण को बाधाओं में कई वस्तुओं तक बढ़ाया जा सकता है। –
धन्यवाद, मैं इस अवधारणा का उपयोग करके एक साधारण कोड को लागू करने की कोशिश कर रहा हूं, इसे समाप्त करने के बाद इसे एएसएपी स्वीकार करूँगा ... – shole