题解 | #【模板】01背包#

主要思路是利用dp找到0-V中每个大小的背包放满可以得到的最大价值。整个背包可放的最大价值就是dp的最大值。dp的最后一个数dp[v]就是放满V大小的背包的最大价值的值。如果没有最大值就输出初始化时候的0，满足输出要求

while True:
    try:
        n, V = map(int, input().split())
        lv, lw = [], []
        for i in range(n):
            l = list(map(int, input().split()))
            lv.append(l[0])  # 物品重量列表
            lw.append(l[1])  # 物品价值列表
        # 2 双结果dp[j]
        dp = [0 for _ in range(V + 1)] # dp[j]表示背包容量为j时装满背包的最大价值。最终输出时，问题1的答案是整个dp的最大值，问题2的答案是dp的最后一个数，初始化时数字是0所以最后如果的不到结果也满足答案要求。
        for i in range(n):
            for j in range(V, -1, -1):  # 从后向前算，防止数据混淆
                if lv[i] <= V and(j == lv[i] or (dp[j - lv[i]] != 0 and j - lv[i] > 0)):  # 条件首先剔除无法放入背包的物品。然后如果新加入的物品可以单独放入某一个j、或者与已存在的值可以组成j的值进行计算。由于Python的特性dp需剔除负坐标j - lv[i] > 0
                    dp[j] = max(dp[j], dp[j - lv[i]] + lw[i])  # dp[j]的值只与其当前值、能与lv[i]重量组合成j重量的dp[j - lv[i]]，两个数中的较大值
        print(max(dp))
        print(dp[-1])
    except:
        break