0-1 背包问题的 Python 程序

在本文中，我们将学习如何解决下面给出的问题陈述。

问题陈述 - 我们给出了 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 背包问题编写 Python 程序。

Pavitra

更新于： 2019 年 12 月 20 日

5 千次+浏览

启动你的 职业

完成课程获得认证

开始