和01背包的区别是每种物品的个数是无限的。
void solve_1() { for(int i=1; i<=n; i++) for(int j=1; j<=W; j++) { dp[i][j]=-1; for(int k=0; k*w[i]<=j; k++) dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]); } }
化简：
void solve_3() { for(int i=1; i<=n; i++) for(int j=1; j<=W; j++) { dp[i][j]=dp[i-1][j]; if(w[i]<=j) dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]); } }
可以优化成一维数组：
void solve_5() { //初始化 memset(dp_reuse,0,sizeof(dp_reuse)); for(int i=1; i<=n; i++) for(int j=w[i]; j<=W; j++) dp_reuse[j]=max(dp_reuse[j],dp_reuse[j-w[i]]+v[i]); }
https://blog.csdn.net/ACM_hades/article/details/89190424
原文：https://www.cnblogs.com/h694879357/p/12301349.html