如果题目对拿的物品的件数也有限制的话,该怎么写呢?
就比如说第 i 件物品有 m[i] 件,且整个背包装的物品件数不能超过 k 件。其它和多重背包的模板一样。
求枚举件数及状态转移的代码。
比如,如下是多重背包的模板代码:
for (int i=1; i<=n; i++){
for (int j=v; j>=0; j--){
for(int k=1; k<=min(m[i], j/w[i]); k++) f[j]=max(f[j], f[j-k*w[i]]+k*s[i]);
}
}
其中,第 3 行就是枚举件数并状态转移的代码。
顺便问一下该题的难度大概是多少?