AcWing 多重背包问题I

问题如下有 N种物品和一个容量是 V的背包。第 i 种物品最多有 si件每件体积是 vi价值是 wi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数NV用空格隔开分别表示物品种数和背包容积。接下来有 N行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0N,V≤1000vi,wi,si≤100输入样例4 51 2 32 4 13 4 34 5 2输出样例10思路与代码思路1暴力拆解法把 s[i] 件相同的物品拆成 s[i] 个独立的物品然后做0-1背包。完整代码如下#includestdio.hintmax(inta,intb){returnab?a:b;}intmain(){intN,V;scanf(%d %d,N,V);intdp[1005]{0};for(inti0;iN;i){intv,w,s;scanf(%d %d %d,v,w,s);// 把s件物品拆成s个独立的for(intk0;ks;k){// 对每个拆出来的物品做0-1背包for(intjV;jv;j--){dp[j]max(dp[j],dp[j-v]w);}}}printf(%d\n,dp[V]);return0;}暴力拆解法当s过于大时缺点暴露就会很明显而这个时候我们可以采用另一种方法思路2二进制优化法首先我们知道任何一个数都可以拆解成二进制数的和拆分规则如下intk1;while(sk){// 拆出一件组合物品体积k*v价值k*w// 这个组合物品代表选k件原物品s-k;k*2;}if(s0){// 最后剩下的s件}根据这样的拆分规则我们在进行01背包的方法即可完成解题完整代码如下#includestdio.hintmax(inta,intb){returnab?a:b;}intmain(){intN,V;scanf(%d %d,N,V);intdp[1005]{0};for(inti0;iN;i){intv,w,s;scanf(%d %d %d,v,w,s);// 二进制拆分intk1;while(sk){// 拆出一件组合物品intnew_vk*v;intnew_wk*w;// 对这个组合物品做0-1背包for(intjV;jnew_v;j--){dp[j]max(dp[j],dp[j-new_v]new_w);}s-k;k*2;}// 处理剩余部分if(s0){intnew_vs*v;intnew_ws*w;for(intjV;jnew_v;j--){dp[j]max(dp[j],dp[j-new_v]new_w);}}}printf(%d\n,dp[V]);return0;}