2023年8月1日发(作者：)

多重背包问题（python实现），动态规划多重背包问题多重背包和01背包以及完全背包问题的区别在于：每个物品的数量是给定的，既不是01背包中的1个，也不是完全背包中的⽆穷多个。其实这个和完全背包那个三重循环的解法很像，如果那个能理解，这个也不在话下了。先上代码：import numpy as npdef solution(max_weight,weight,value,num): dp = ((len(weight)+1,max_weight+1),dtype=int) for i in range(1,len(weight)+1): for j in range(1,max_weight+1): if weight[i-1] > j: dp[i][j] = dp[i-1][j] else: count = min(num[i-1],j//weight[i-1]) dp[i][j] = dp[i-1][j] for k in range(1,count+1): temp = dp[i-1][j-k * weight[i-1]] + k * value[i-1] if temp > dp[i][j]: dp[i][j] = temp print(dp) return dp数据：weight = [1,2,2]value = [6,10,20]num = [10,5,2]背包容量：8分析程序：还是先创建⼀个⼆维数组dp，由于是多重背包，所以对于⼀个物品i（假设i=3，是3号物品），有如下选择：不拿，那么就⽤当前的可⽤空间去装3号物品之前的物品（也就是1、2号）。拿，那么拿⼏件呢？在拿的时候要注意不能超过给定的数量，也不能使物品重量超过背包容量。所以在代码中，如果j⼤于当前物品单个的重量，就要算出最多能拿多少个count = min(num[i-1],j//weight[i-1])⽤min是因为如果背包容量太⼤，能装下物品地数量就⼤于给定数量了，因此⽤num[i-1]来做上界。紧接着 dp[i][j] = dp[i-1][j] ，是考虑到了不选当前物品⽐选更优的情况。接着for k in range(1,count+1): temp = dp[i-1][j-k * weight[i-1]] + k * value[i-1] if temp > dp[i][j]: dp[i][j] = temp对能拿的物品数量遍历，循环结束后会解出最优⽅案（是不拿，还是拿1个、2个…）下⾯的代码能将选了什么物品输出：def things(max_weight,dp,weight,value,num): raw = len(weight) col = max_weight remain = dp[raw][col] goods = [0,0,0] while remain != 0: if remain != dp[raw-1][col]: count = min(num[raw-1],col//weight[raw-1]) for k in range(1,count+1): if dp[raw][col] - k * value[raw-1] == dp[raw-1][col-k * weight[raw-1]]: remain -= k * value[raw-1] col -= k * weight[raw-1] goods[raw-1] = k raw -= 1 print(goods)分析程序：if remain != dp[raw-1][col]这句，是看看拿没拿当前物品，如果左右相等说明没拿。如果不等，再往下看：count = min(num[raw-1],col//weight[raw-1]) 是把能装多少个物品求出来。if dp[raw][col] - k * value[raw-1] == dp[raw-1][col-k * weight[raw-1]] 这⾏的意思是，现在的背包状态拿出k个当前物品，剩余的价值是否等于 前⾯的物品和除去这k个物品所占的重量的价值。若相等，说明就是拿了k个当前物品。输出：[4, 0, 2]第⼀个物品拿4个，第三个物品拿2个。

2023年8月1日发(作者：)

多重背包问题（python实现），动态规划多重背包问题多重背包和01背包以及完全背包问题的区别在于：每个物品的数量是给定的，既不是01背包中的1个，也不是完全背包中的⽆穷多个。其实这个和完全背包那个三重循环的解法很像，如果那个能理解，这个也不在话下了。先上代码：import numpy as npdef solution(max_weight,weight,value,num): dp = ((len(weight)+1,max_weight+1),dtype=int) for i in range(1,len(weight)+1): for j in range(1,max_weight+1): if weight[i-1] > j: dp[i][j] = dp[i-1][j] else: count = min(num[i-1],j//weight[i-1]) dp[i][j] = dp[i-1][j] for k in range(1,count+1): temp = dp[i-1][j-k * weight[i-1]] + k * value[i-1] if temp > dp[i][j]: dp[i][j] = temp print(dp) return dp数据：weight = [1,2,2]value = [6,10,20]num = [10,5,2]背包容量：8分析程序：还是先创建⼀个⼆维数组dp，由于是多重背包，所以对于⼀个物品i（假设i=3，是3号物品），有如下选择：不拿，那么就⽤当前的可⽤空间去装3号物品之前的物品（也就是1、2号）。拿，那么拿⼏件呢？在拿的时候要注意不能超过给定的数量，也不能使物品重量超过背包容量。所以在代码中，如果j⼤于当前物品单个的重量，就要算出最多能拿多少个count = min(num[i-1],j//weight[i-1])⽤min是因为如果背包容量太⼤，能装下物品地数量就⼤于给定数量了，因此⽤num[i-1]来做上界。紧接着 dp[i][j] = dp[i-1][j] ，是考虑到了不选当前物品⽐选更优的情况。接着for k in range(1,count+1): temp = dp[i-1][j-k * weight[i-1]] + k * value[i-1] if temp > dp[i][j]: dp[i][j] = temp对能拿的物品数量遍历，循环结束后会解出最优⽅案（是不拿，还是拿1个、2个…）下⾯的代码能将选了什么物品输出：def things(max_weight,dp,weight,value,num): raw = len(weight) col = max_weight remain = dp[raw][col] goods = [0,0,0] while remain != 0: if remain != dp[raw-1][col]: count = min(num[raw-1],col//weight[raw-1]) for k in range(1,count+1): if dp[raw][col] - k * value[raw-1] == dp[raw-1][col-k * weight[raw-1]]: remain -= k * value[raw-1] col -= k * weight[raw-1] goods[raw-1] = k raw -= 1 print(goods)分析程序：if remain != dp[raw-1][col]这句，是看看拿没拿当前物品，如果左右相等说明没拿。如果不等，再往下看：count = min(num[raw-1],col//weight[raw-1]) 是把能装多少个物品求出来。if dp[raw][col] - k * value[raw-1] == dp[raw-1][col-k * weight[raw-1]] 这⾏的意思是，现在的背包状态拿出k个当前物品，剩余的价值是否等于 前⾯的物品和除去这k个物品所占的重量的价值。若相等，说明就是拿了k个当前物品。输出：[4, 0, 2]第⼀个物品拿4个，第三个物品拿2个。