算法1: 最朴素的做法(运行时间 1265 ms)

按照原先商品的顺序, 并且对所有的体积进行遍历
dp[i][j]的定义与大雪菜的定义不太一样, 表示前i个商品, 体积正好等于j时的最大价值.
利用覆盖法, 压缩了第一维.

时间复杂度

O(N * V)

Python 代码

N, V = map(int, input().split())
dp = [float("-inf")] * (V + 1)
dp[0] = 0
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
for i in range(N):
    for j in range(V, A[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - A[i][0]] + A[i][1])
print(max(dp))

算法2: 每次对体积的循环的时候, 上限设置为实际的上限 (运行时间: 1093 ms)

比如V = 1000
商品的体积分别为1, 10, 5
那么, 对商品1进行循环的时候, 体积的实际上限应该为1, 更大的体积是无法达到的
对商品1进行循环的时候, 体积的实际上限应该为1 + 10, 更大的体积是无法达到的
对商品2进行循环的时候, 体积的实际上限应该为1 + 10 + 5, 更大的体积是无法达到的

时间复杂度

O(N * V)

Python 代码

N, V = map(int, input().split())
dp = [float("-inf")] * (V + 1)
dp[0] = 0
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
s = 0
for i in range(N):
    if s < V:
        s += A[i][0]
        s = min(s, V)
    for j in range(s, A[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - A[i][0]] + A[i][1])
print(max(dp))

算法3: 基于体积对商品进行排序 (运行时间: 1012 ms)

算法3是对算法2的优化.
基于体积对商品进行排序, 目的是为了让二重循环的迭代次数最小化

时间复杂度

O(N * log(N) + N * V)

Python 代码

N, V = map(int, input().split())
dp = [float("-inf")] * (V + 1)
dp[0] = 0
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
A.sort()
s = 0
for i in range(N):
    if s < V:
        s += A[i][0]
        s = min(s, V)
    for j in range(s, A[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - A[i][0]] + A[i][1])
print(max(dp))