题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

样例

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

算法1

时间复杂度

参考文献

Python3 代码

n, m = map(int, input().split())
v = [0] * 1010
w = [0] * 1010
f = [0] * 1010
for i in range(n):
    a, b = map(int, input().split())
    v[i] = a
    w[i] = b
for i in range(n):
    for j in range(m, -1, -1):
        if j >= v[i]:
            f[j] = max(f[j], f[j-v[i]] + w[i])
print(f[m])