完全背包问题

链接

https://www.acwing.com/problem/content/description/3/

题解

0-1背包的限制是，每件物品只能选一次 而完全背包的每个物品可以选无数次，直到背包装不下

只需对0-1背包的状态转移方程稍稍做个改变即可

0-1背包的状态转移方程： dp[i][j] = max( dp[i][j-v[i]]+w[i],dp[i-1][j]) 每次算最大价值时，只会减去一次物品的体积，加上一次物品的价值，相当于选了一次物品 这里需要改成选无数次，直到背包装不下

假设当前背包的容量为j，取某一件物品的的个数为k 那么

for(int k = 0; k*v[i] <= j; k++){
    dp[i][j] = max( dp[i][j-k*v[i]]+k*w[i],dp[i][j])
}