【leetcode】背包问题

JNingWei

发布于 2020-06-02 10:44:33

5510

发布于 2020-06-02 10:44:33

文章被收录于专栏：JNing的专栏

思路

一般用动态规划（DP）。

输入参数

W:各个物品的重量；
V:各个物品的价值；
carry:最大承重为carry的背包；
N：物品件数。

0-1背包

每件物品只能选一次。

def bag_01(V, W, carry, N):
    res = [0] * (carry+1)
    for i in range(N):
        for j in range(carry, W[i]-1, -1):
            res[j] = max(res[j], res[j-W[i]]+V[i])
    return res[-1]

完全背包

每件物品可以选无数次。

完全背包的特点恰是每种物品可选无限件，所以就可以并且必须采用 w = W[i]…carry 的顺序循环：

def bag_absolute(V, W, carry, N):
    res = [0] * (carry+1)
    for i in range(N):
        for j in range(W[i], carry+1):	# 这是和01背包唯一的区别:正序遍历
            res[j] = max(res[j], res[j-W[i]]+V[i])
    return res[-1]

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/05/31 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dp