文章目录
题目描述
对比01背包,完全背包中的每件物品有无数件。
也就是说,每件物品可以拿0,1,…,k,…件。
状态(和01背包一样)
dp[i][j]表示前i种物品,体积为j时的最大价值
状态转移
- 对于第i件物品: - 不拿:dp[i][j]⇐dp[i-1][j]- 拿一件:dp[i][j]⇐dp[i-1][j-w[i]]+v[i]- 拿两件:dp[i][j]⇐dp[i-1][j-2w[i]]+2v[i]- …- 拿k件:dp[i]][j]⇐dp[i-1][j-kw[i]]+kv[i]
状态转移方程
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − k ∗ w [ i ] ] + k ∗ w [ i ] ) , k = 1 , . . . , j w [ i ] dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*w[i]),k=1,...,\frac{j}{w[i]} dp[i][j]=max(dp[i−1][j],dp[i−1][j−k∗w[i]]+k∗w[i]),k=1,...,w[i]j
- 展开 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] , d p [ i − 1 ] [ j − 2 ∗ w [ i ] ] + 2 ∗ v [ i ] , . . . ) ( 1 + j w [ i ] 项 ) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i],dp[i-1][j-2w[i]]+2v[i],...)(1+\frac{j}{w[i]}项) dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i],dp[i−1][j−2∗w[i]]+2∗v[i],...)(1+w[i]j项)
d p [ i ] [ j − w [ i ] ] = m a x ( d p [ i − 1 ] [ j − w [ i ] ] , d p [ i − 1 ] [ j − 2 ∗ w [ i ] ] + ∗ v [ i ] , . . . ) ( j w [ i ] 项 ) dp[i][j-w[i]]=max(dp[i-1][j-w[i]],dp[i-1][j-2*w[i]]+*v[i],...)(\frac{j}{w[i]}项) dp[i][j−w[i]]=max(dp[i−1][j−w[i]],dp[i−1][j−2∗w[i]]+∗v[i],...)(w[i]j项)
- 综上可得dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])
- 直观上理解为:前一项表示不取第i种,后一项表示在先前的基础上取第i种(取多次)
代码
n,V=map(int,input().split())
dp=[[0]*(V+1)for _ inrange(n+1)]for i inrange(1,n+1):
w,v=map(int,input().split())for j inrange(V+1):if j<w:
dp[i][j]=dp[i-1][j]else:
dp[i][j]=max(dp[i-1][j],dp[i][j-w]+v)print(dp[n][V])
滚动数组优化
…i-1,ji,j-w[i]i,j
可见,更新dp[i][j]时,用的是同一行先前位置dp[i][j-w[i]]和上一行对应位置的dp[i-1][j],和01数组不同在于更新方向。
使用单个数组更新时,采用从小到大的方向对dp数组进行覆盖。
n,V=map(int,input().split())
dp=[0]*(V+1)for i inrange(1,n+1):
w,v=map(int,input().split())for j inrange(w,V+1):
dp[j]=max(dp[j],dp[j-w]+v)print(dp[V])
版权归原作者 sml_5421 所有, 如有侵权,请联系我们删除。