【python】非0-1背包问题的简单解法

上一篇关于背包问题的文章里面，我讲述了一个比较简单的背包问题的解法，但是这种背包问题只是最基础的0-1背包问题，既每个物品只能选择0个或者1个，但是背包问题不止有这一种，还有另外两种：完全背包和多重背包，而这两种背包问题就分别需要不同的解法
完全背包
完全背包的定义和0-1背包的区别就是0-1背包每个物品只能用一次，而完全背包每个物品能用无限次，这看起来很麻烦，其实我们只需要在原本的代码中加入几行代码就可以解决
这里我先把上次的代码展示出来

from itertools import *
u = []
v = []
s = int(input("背包容量："))
t = int(input("物品数量："))
for i in range(t):
    u.append(int(input(f"第{i+1}个物品重量：")))
    v.append(int(input(f"第{i+1}个物品价值：")))
a = []
for i in range(len(u)):
    q = [u[i], v[i]]
    a.append(q)

a=list(permutations(a))

al=[]
for i in a:
    al.append(list(i))
    

gdl=[]
for x in al:  # x是一种情况，示例：[[1(重量),2(价值)],[1(重量),2(价值)]]
    jz = 0
    wt = 0
    jq = len(x)-1
    for y in x:  # y是一组数据，示例：[1(重量),2(价值)]
        
        jz+=y[1]
        wt+=y[0]
        
    while True:
            
        if wt>s:
            wt -= x[jq][0]
            jz -= x[jq][1]
            jq -= 1

        if wt<=s:
            gdl.append(jz)
            break

print(max(gdl))

其实我们只需要在6-8行做出改动，其他的就不用管了
而所作出的改动呢，就是把所有的物品都多添加几次，比如说背包容量是10，有重量为4的物品，那么这个背包最多装下两个这样的物品，这样只需要把这个物品的数据添加两次到储存物品数据的列表里面就可以了
其他的代码就不再次重复了，就看改动后的代码：

for i in range(t):
	weight=int(input(f"第{i+1}个物品重量："))
	money=int(input(f"第{i+1}个物品价值："))
	for it in range(int(s/weight)):
    	u.append(weight)
    	v.append(money)

改成这样子之后，就可以把每个物品都保存这个背包能装下的最大数量次，之后就可以按上次的代码运行，然后完全背包问题就無了

多重背包
多重背包问题论难度还没有完全背包问题大，只要根据所给的物品的数量来储存到列表里面就可以了，还是基础代码不变，采集数据这一块变动。

for i in range(t):
	weight=int(input(f"第{i+1}个物品重量："))
	money=int(input(f"第{i+1}个物品价值："))
	num=int(input(f"第{i+1}个物品的数量："))
	for it in range(num):
    	u.append(weight)
    	v.append(money)

根据给出的物品数量添加相应数量的物品，就可以完成数据的采集
总结
完全背包和多重背包问题和基础的0-1背包问题的主体变动为零，只需要在数据采集方面做出一些改动，就可以解决。
tips：白嫖代码的时候记得检查代码的格式，不然会导致…