python多重背包问题,已有最佳值,如何获得该最佳的具体方案 5C

def MultiplePack(N, V, weight, value, num):
"""
多重背包问题(每个物品都有次数限制)
:param N: 物品个数, 如 N=5
:param V: 背包总容量, 如V=15
:param weight: 每个物品的容量数组表示, 如weight=[5,4,7,2,6]
:param value: 每个物品的价值数组表示, 如value=[12,3,10,3,6]
:param num: 每个物品的个数限制,如num=[2,4,1,5,3]
:return: 返回最大的总价值
"""

# 初始化f[N+1][V+1]为0,f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
f = [[0 for col in range(V + 1)] for row in range(N + 1)]
g = [[0 for col in range(V + 1)] for row in range(N + 1)]
for i in range(1, N+1):
    for j in range(1, V+1):
        # 对于物品i最多能取的次数是j/weight[i-1]与num[i-1]中较小者
        max_num_i = int(min(j/weight[i-1], num[i-1]))
        f[i][j] = f[i - 1][j]  # 初始取k=0为最大,下面的循环是把取了k个物品i能获得的最大价值赋值给f[i][j]
        for k in range(max_num_i+1):
            if f[i][j] < f[i-1][j-k*weight[i-1]]+k*value[i-1]:
                f[i][j] = f[i-1][j-k*weight[i-1]]+k*value[i-1]  # 状态方程
max_value = f[N][V]
return max_value

print(MultiplePack(3,1585,[807,797,787],[807,797,787],[6,5,2]))

以上为获得最佳值的代码,运行后为1584,但还想知道具体方案是怎么样的比如上面这个例子里 1584 = 797*1+787*1 等式后面部分如何编入代码获取,求完善代码,谢谢大神们

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!