0-1背包

类似于0-1背包, 只是需要多考虑方案数.

时间复杂度

O(N * V)

Python 代码

MOD = 10 ** 9 + 7
N, V = map(int, input().split())

# dp[j], 返回一个长度为2的tuple, 表示体积恰好等于j时的最大价值与方案个数
# 当体积为0时, 初始化为(0, 1), 表示价值为0, 方案个数为1
# 其他体积时, 初始化为(-inf, 0), 目前无法到达这个体积, 因此, 价值为-inf, 方案个数为0
dp = [[float("-inf"), 0] for _ in range(V + 1)]
dp[0][0] = 0
dp[0][1] = 1

# 使用0-1背包差不多的算法, 只是需要多考虑方案个数
for i in range(N):
    v, w = map(int, input().split())
    for j in range(V, v - 1, -1):
        a = dp[j][0]
        b = dp[j - v][0] + w
        if a == b:
            dp[j][1] = (dp[j][1] + dp[j - v][1]) % MOD
        elif a < b:
            dp[j][0] = dp[j - v][0] + w
            dp[j][1] = dp[j - v][1]

# 容易出错的点: 不同体积下, 有可能同时取到最大价值, 这个时候, 方案个数应该相加
ans = float("-inf")
cnt = 0
for i in range(V + 1):
    if dp[i][0] > ans:
        ans = dp[i][0]
        cnt = dp[i][1]
    elif dp[i][0] == ans:
        cnt = (cnt + dp[i][1]) % MOD
print(cnt)