50万县城做地方网站,2018年主流网站开发语言,微网站开发怎么写,怎么做网页推广多重背包简介#xff1a; 有N种物品和一个容量为V的背包。第i种物品最多有Mi件可用#xff0c;每件耗费的空间为Ci#xff0c;价值为Wi。求解将哪些物品装入背包可使得这些物品耗费的空间总和不超过背包容量#xff0c;且价值总和最大。 将Mi件摊开#xff0c;就是一个01背…多重背包简介 有N种物品和一个容量为V的背包。第i种物品最多有Mi件可用每件耗费的空间为Ci价值为Wi。求解将哪些物品装入背包可使得这些物品耗费的空间总和不超过背包容量且价值总和最大。 将Mi件摊开就是一个01背包问题。 如下列两表就是等价的图来源于代码随想录。
void test_multi_pack()
{vectorint weight {1,3,4};vectorint value {15,20,30};vectorint nums {2,3,2};int bagWeight 10;//进行展开转化为01背包问题for(int i 0; i nums.size(); i){while(nums[i] 1) {//nums[i]保留到1把其他的多余的个数展开weight.push_back(weight[i]);value.push_back(value[i]);nums[i]--;}}vectorint dp(bagWeight 1, 0);for(int i 0; i weight.size(); i) //遍历物品{for(int j bagWeight; j weight[i]; j--) //遍历背包容量{dp[j] max(dp[j],dp[j-weight[i]] values[i])}}cout dp[bagWeight] endl;
}
