当前位置:   article > 正文

python的0/1背包最大价值问题详解_python 0 1背包

python 0 1背包

第一:0/1背包问题是一个什么样的问题?

0/1背包问题是一个经典的动态规划问题。它的问题描述是:给定一组物品,每个物品有一个重量和一个价值,还有一个背包的容量限制。需要选择一些物品放入背包中,使得放入背包的物品的总重量不超过背包的容量限制,同时使得放入背包的物品的总价值最大。

问题描述: 有n个物品,每个物品的重量分别为w1, w2, ..., wn,价值分别为v1, v2, ..., vn,背包的最大承重为W。求解如何选择物品使得物品的总价值最大化,且总重量不超过背包的承重。

解决方案:

  1. 创建一个二维数组dp,大小为(n+1) x (W+1),其中dp[i][j]表示在前i个物品中选择总重量不超过j的物品的最大价值。
  2. 初始化dp数组的第一行和第一列为0。
  3. 遍历物品列表,对于每个物品i,遍历背包的承重j从1到W,计算以下两种情况:
    • 不选择物品i:dp[i][j] = dp[i-1][j]
    • 选择物品i:dp[i][j] = dp[i-1][j-wi] + vi 在这两种情况中选择较大的价值作为dp[i][j]的值。

v代表value价值,w代表weight重量

第二:0/1背包问题示例:

下面是一个简单的Python实现:

  1. def knapsack(weights, values, capacity):#定义一个背包有参函数
  2. n = len(weights) # 物品的数量,通过重量这个列表得到物品的数量。
  3. # 这段代码创建了一个二维数组 dp,其大小为 (n+1) × (capacity+1),并且初始化所有元素为0。
  4. dp = [[0] * (capacity + 1) for _ in range(n + 1)]
  5. # 动态规划的过程
  6. for i in range(1, n + 1):
  7. for j in range(1, capacity + 1):
  8. # 如果当前物品的重量大于背包的容量限制,则不选择当前物品
  9. if j < weights[i-1] :
  10. dp[i][j] = dp[i-1][j]
  11. else:
  12. # 否则,选择当前物品或者不选择当前物品,取价值最大的情况
  13. dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])
  14. # 返回最优解(即最大价值)
  15. return dp[n][capacity]
  16. weights = [2, 3, 4, 5] # 物品的重量
  17. values = [3, 4, 5, 6] # 物品的价值
  18. capacity = 8 # 背包的容量限制
  19. result = knapsack(weights, values, capacity)
  20. print("最大价值:", result)

如上:

已知状态转移方程

判别条件结果原因
j < weights[i-1] dp[i][j] = dp[i-1][j]装不下
j >= weights[i-1]  dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])装得下

 

运行结果为:

第二个举例展示:

  1. w=[3,2,1,4,5]
  2. v=[25,20,15,40,50]
  3. n=len(w)
  4. capacity=6
  5. dp = [[0] * (capacity + 1) for _ in range(n +1 )]
  6. for i in range(1,n+1):
  7. for j in range(1,capacity+1):
  8. if j<w[i-1]:
  9. dp[i][j]=dp[i-1][j]
  10. else :
  11. dp[i][j]=max(dp[i-1][j-1],v[i-1]+dp[i-1][j-w[i-1]])
  12. print("最大价值为:",dp[i][j])

请注意i为物品的实时数量,j为实时容量。

j为0表示此时可装入物品重量为0,i为0表示可装入物品数量为0。
 

运行结果展示:

这个实现的时间复杂度为O(n*capacity),其中n是物品的数量,capacity是背包的容量限制。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/466349
推荐阅读
相关标签
  

闽ICP备14008679号