AcWing 11. 背包问题求方案数(Python)
原题链接
中等
作者:
今天AC了吗
,
2022-02-25 18:06:23
,
所有人可见
,
阅读 479
背包问题求方案数
算法分析(和yxc思路不一样的做法)
- dp数组的定义:
dp[i][j]
表示从前i个物品中选,总体积不超过j的方案的最大价值
- g计数数组定义:
g[i][j]
表示从前i个物品中,总体积不超过j的方案总数
- g数组的初始化:
g[0][0] ~ g[0][V]
中此时物品体积为0,且都不超过总体积,满足条件所以全初始化为1
- dp数组的递推关系:与01背包思路一致(所以可以将二维空间降为一维)
- g数组的递推关系:情况一.
dp[j-v] > dp[j]
那么g[j]
数组就等于g[j-v]
的方案数;
情况二:dp[j-v]<dp[j]
因为以及将空间降为一维此时的g[j]
就表示上层的方案数;
情况三:dp[j-v]==dp[j]
则将前两种情况的方案数相加即可。
Python 代码
n,V = map(int,input().split())
dp = [0 for j in range(V+1)]
g = [1 for j in range(V+1)]
mod = 10**9+7
for i in range(1,n+1):
v,w = map(int,input().split())
for j in range(V,v-1,-1):
if dp[j] == dp[j-v]+w:
g[j] += g[j-v]
elif dp[j] < dp[j-v]+w:
g[j] = g[j-v]
dp[j] = max(dp[j], dp[j-v]+w)
print(g[V]%mod)