想问下大神python的背包问题的源代码(最好玩也有伪代码,请用递归法实...

发布网友发布时间：2024-10-09 16:28

共1个回答

热心网友时间：2024-10-15 19:29

递归有层数限制，所以最好不要用，能不用就不用，没有想到什么好的算法，弄了个简单粗暴的，包容量除以最小质量的，就是最多可以装多少个，然后全排列一遍三种商品，并计算价值，取最大的一个价值，代码如下：

a, b, c = 2, 2.5, 3           # 三种商品质量
A, B, C = 4, 5, 6             # 三种商品价值
m = 100                       # 包容量
ds = int(100 / min(a, b, c))  # 最小质量取到最大数量

mx = 0                        # 最大价值
nl = []                       # 商品数量列表
for i1 in range(0, ds + 1):   # 全排列
    for i2 in range(0, ds + 1 - i1):
        for i3 in range(0, ds + 1 - i1 - i2):
            # 判断总质量超出则舍弃
            n = i1 * a + i2 * b + i3 * c
            if n > m:
                continue
            # 计算总价值取最高值及排列并存储
            j = i1 * A + i2 * B + i3 * C
            if mx < j:
                mx = j
                nl = [i1, i2, i3]
# 输出最大价值和组合
print(mx)
print(nl)