关于多重背包
  • 板块学术版
  • 楼主rainygame
  • 当前回复18
  • 已保存回复18
  • 发布时间2023/2/26 07:12
  • 上次更新2023/10/23 23:44:56
查看原帖
关于多重背包
804607
rainygame楼主2023/2/26 07:12

如果题目对拿的物品的件数也有限制的话,该怎么写呢?

就比如说第 ii 件物品有 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]);
	}
}

其中,第 33 行就是枚举件数并状态转移的代码。

顺便问一下该题的难度大概是多少?

2023/2/26 07:12
加载中...