Add 权值较为复杂的多重背包

[cbs001]

页面英文名

No response

我希望能添加的内容是

对于这样一个多重背包：买 N 件 i 物品，可以得到 A[i]*N+B[i] 的价值。

可以发现，第一次买可以得到 A[i]+B[i] 的价值。再次买可以得到 A[i] 的价值。

由此可以拆分成01背包和完全背包求解

for(int i=1; i<=n; i++){
for(int j=v; j>=w[i]; j--) dp[j]=max(dp[j],dp[j-w[i]]+a[i]+b[i]);
for(int j=w[i]; j<=v; j++) dp[j]=max(dp[j],dp[j-w[i]]+a[i]);
}

我了解到的相关参考资料有

https://acm.hdu.edu.cn/showproblem.php?pid=5410

CRB and His Birthday

[welcome]

感谢你对 OI Wiki 的关注！记得在 Issue 中表达清楚自己的意思哦～