首页 > 试题广场 >

假定在0-1背包问题中，商品的重量递增序与价值递减序完全一样

[问答题]
假定在0-1背包问题中，商品的重量递增序与价值递减序完全一样。设计一个高效的算法求解背包问题的变形的最优解，证明你的算法是正确的。
添加回答
爱吃烤肠的代码渣渣在参加牛客活动头像 爱吃烤肠的代码渣渣在参加牛客活动 
W = 20
n = 5
w = [2, 3, 4, 5, 9]
v = [3, 4, 5, 8, 10]
# 初始化: 全为0
dp = [0] * (W + 1)
# 先遍历物品, 再遍历背包容量
for i in range(n):
    for j in range(w[i]-1,W,  -1): # 背包容量在w[i]与W之间才能装下物品i，倒序遍历是为了保证物品i只被放入一次。
        value1 = dp[j - w[i]] + v[i] # 装
        value2 = dp[j] # 不装
        dp[j] = max(value1, value2)
print(dp)
print(dp[-1])
发表于 2023-03-09 14:11:50 回复(0)
逝。头像 逝。
那我只需考虑容量最大化即可
发表于 2020-02-21 22:07:02 回复(0)
提交观点

问题信息

上传者：小小
难度：
2条回答 2095浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号