讨论/《算法图解》 - 9.2 背包问题 FAQ/
《算法图解》 - 9.2 背包问题 FAQ
共 16 个回复

9.1 假设你还可偷另外一件商品——MP3 播放器,它重 1 磅,价值1000美元。你要偷吗?

1.png

  • 最高价值是4500,选择是iPhone(I) + 吉他(G) + MP3(3)

9.2 假设你要去野营。你有一个容量为 6 磅的背包,需要决定该携带下面的哪些东西

2.png

  • 最高价值是25,选择是水(W) + 食物(F) + 相机(C)

代码验证

def max_value(capacity: int, weights: list[int], values: list[int], names: list[str]) -> int:
    """
    背包问题
    :param capacity:    背包最大容量
    :param weights:     每一件物品的重量
    :param values:      每一件物品的价值
    :param names:       每一件物品的名称
    :return:            这个背包可以容纳物品的最大价值
    """
    # 存储最大价值
    dp = [[0] * (capacity + 1) for _ in range(len(weights))]
    # 存储选择的物品
    path = [[''] * (capacity + 1) for _ in range(len(weights))]

    # 由于python的-1会取最后一个元素,但其它语言需要注意(i - 1 < 0)的情况
    for i in range(len(weights)):
        for w in range(capacity + 1):
            # 计算前i件在最大容量为w下时,可获得的最高价值
            if weights[i] <= w and dp[i - 1][w] <= dp[i - 1][w - weights[i]] + values[i]:
                dp[i][w] = dp[i - 1][w - weights[i]] + values[i]
                path[i][w] = f'{path[i - 1][w - weights[i]]}{names[i]}'
            else:
                dp[i][w] = dp[i - 1][w]
                path[i][w] = path[i - 1][w]

    # 打印最大价值及其选择的物品
    for i in range(len(dp)):
        for j in range(1, len(dp[i])):
            print(f'{dp[i][j]}({path[i][j]})'.rjust(12), end='')
        print()

    return dp[-1][-1]

9.1 运行结果

---- 输入 ----
max_value(4, [1, 4, 3, 1, 1], [1500, 3000, 2000, 2000, 1000], ['G', 'S', 'L', 'I', 'M'])
---- 输出 ----
1500(G)     1500(G)     1500(G)     1500(G)
1500(G)     1500(G)     1500(G)     3000(S)
1500(G)     1500(G)     2000(L)    3500(GL)
2000(I)    3500(GI)    3500(GI)    4000(LI)
2000(I)    3500(GI)   4500(GIM)   4500(GIM)

9.2 运行结果

---- 输入 ----
max_value(6, [3, 1, 2, 2, 1], [10, 3, 9, 5, 6], ['W', 'B', 'F', 'J', 'C'])
---- 输出 ----
 0()         0()       10(W)       10(W)       10(W)       10(W)
3(B)        3(B)       10(W)      13(WB)      13(WB)      13(WB)
3(B)        9(F)      12(BF)      13(WB)      19(WF)     22(WBF)
3(B)        9(F)      12(BF)      14(FJ)      19(WF)     22(WBF)
6(C)       9(BC)      15(FC)     18(BFC)     20(FJC)     25(WFC)
9

动态规划一直都没学好,看这个感觉还是很好理解的,看完得趁着热乎的劲再多刷刷题巩固下才行

3

微信读书上可以免费看哦,我觉得读书节就是为了让你找到一些合你胃口的书,遇到一本觉得合适的书才是关键的。

3

畅快至极,畅快至极,不知道为啥就开放几小节,看了也学不了一套,也是浪费时间,意思是让我尝试,然后觉得好再买,这读书节成了又一个消费节,可恶。

4

这是我的两条测试数据

print(max_value(4, [1, 4, 3, 1, 1], [1500, 3000, 2000, 2000, 1000], ['G', 'S', 'L', 'I', 'M']))
print(max_value(6, [3, 1, 2, 2, 1], [10, 3, 9, 5, 6], ['W', 'B', 'F', 'J', 'C']))
1

你好,这是 Python3 引入的f-string。f-string 用大括号 {} 表示被替换字段,{} 里面可以是字符串或者表达式。具体的用法可以搜索一下"python3 fstring"

1

书非借而不读,感觉试读更能激发学习欲~

1

学习了学习了!

打卡

很不错呀,讲解细致,如果有动态ppt链接就更好了