रैखिक प्रोग्रामिंग एल्गोरिदम की श्रेणी के तहत knapsack समस्या क्यों शामिल नहीं है, इस तथ्य के बावजूद कि Knapsack समस्या कथन रैखिक प्रोग्रामिंग में समस्याओं के समान लगता है।Knapsack probl को हल क्यों करें। रैखिक प्रोग्रामिंग के रूप में नहीं माना जाता है?
Knapsack को पूर्णांक रैखिक प्रोग्रामिंग प्रोग्राम के रूप में लिखा जा सकता है। सामान्य रैखिक प्रोग्रामिंग के विपरीत, इस समस्या के लिए समाधान में चर पूर्णांक हैं। रैखिक प्रोग्रामिंग बहुपद समय में हल करने योग्य है, जबकि पूर्णांक रैखिक प्रोग्रामिंग एनपी-पूर्ण है।
पाठक के लिए व्यायाम: दिखाएं कि 3 एसएटी को पूर्णांक रैखिक प्रोग्रामिंग में कम किया जा सकता है।
ट्रिविया: MAX-3SAT (3 एसएटी का एक संस्करण जहां हम संतुष्ट क्लॉज की संख्या को अधिकतम करना चाहते हैं) जैसी समस्याओं के लिए अनुमानित एल्गोरिदम हैं। सबसे पहले आप एक पूर्णांक रैखिक कार्यक्रम के रूप में MAX-3SAT लिखते हैं। फिर, आप पूर्णांक प्रतिबंध को हटाकर इसे रैखिक प्रोग्राम में आराम करें। फिर, आप बहुपद समय में रैखिक कार्यक्रम को हल करते हैं। अंत में, यह देखते हुए वास्तविक x मैं ∈ [0,1], तो आप उन्हें पूर्णांकों पर पूर्णांक, या यादृच्छिक पूर्णांक समाधान उत्पन्न y मैं जहां y मैं = 1 की संभावना एक्स मैं है।
एक पूरक के रूप में: http://stackoverflow.com/q/3128001/395857 –
यह ध्यान देने योग्य है कि आम तौर पर आईएलपी को दी गई एनपी समस्या को कम करने के लिए अपेक्षाकृत आसान होता है। –
@ yes123 रैखिक प्रोग्रामिंग में, यह बाधाएं हैं, जो समय नहीं हैं। – fgb