0-1 नैपसैक समस्या के लिए पायथन कार्यक्रम

इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे।

समस्या कथन - हमें n वस्तुओं के वजन और मूल्य दिए गए हैं, हमें इन वस्तुओं को अधिकतम क्षमता w तक क्षमता W के बैग में रखना होगा। हमें अधिकतम संख्या में आइटम ले जाने और उसका मूल्य वापस करने की आवश्यकता है।

आइए अब नीचे दिए गए कार्यान्वयन में समाधान देखें -

# पाशविक बल दृष्टिकोण

उदाहरण

#Returns the maximum value that can be stored by the bag
def knapSack(W, wt, val, n):
   # initial conditions
   if n == 0 or W == 0 :
      return 0
   # If weight is higher than capacity then it is not included
   if (wt[n-1] > W):
      return knapSack(W, wt, val, n-1)
   # return either nth item being included or not
   else:
      return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
         knapSack(W, wt, val, n-1))
# To test above function
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
n = len(val)
print (knapSack(W, wt, val, n))

आउटपुट

350

#गतिशील दृष्टिकोण

उदाहरण

# a dynamic approach
# Returns the maximum value that can be stored by the bag
def knapSack(W, wt, val, n):
   K = [[0 for x in range(W + 1)] for x in range(n + 1)]
   #Table in bottom up manner
   for i in range(n + 1):
      for w in range(W + 1):
         if i == 0 or w == 0:
            K[i][w] = 0
         elif wt[i-1] <= w:
            K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
         else:
            K[i][w] = K[i-1][w]
   return K[n][W]
#Main
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
n = len(val)
print(knapSack(W, wt, val, n))

आउटपुट

350

सभी चर स्थानीय दायरे में घोषित किए गए हैं और उनके संदर्भ ऊपर दिए गए चित्र में देखे गए हैं।

निष्कर्ष

इस लेख में, हमने सीखा है कि हम 0-1 Knapsack Problem के लिए Python Program कैसे बना सकते हैं