题目5. 多重背包问题 II题目描述有N NN种物品和一个容量是V VV的背包。第 i 种物品最多有s i s_isi​件每件体积是v i v_ivi​价值是w i w_iwi​。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数N NNV VV用空格隔开分别表示物品种数和背包容积。接下来有N NN行每行三个整数v i v_ivi​,w i w_iwi​,s i s_isi​用空格隔开分别表示第i ii种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0 N ≤ 1000 0 N ≤ 10000N≤10000 V ≤ 2000 0 V ≤ 20000V≤20000 v i , w i , s i ≤ 2000 0 v_i, w_i, s_i ≤ 20000vi​,wi​,si​≤2000时空限制1s / 64MB输入样例4 5 1 2 3 2 4 1 3 4 3 4 5 2输出样例10思路每个十进制整数都可以转化为二进制数考虑将s[i]用二进制表示s 2 0 s2^0s202 1 2^1212 2 2^222 … 2 k 2^k2kC CC把物品分成每个组每个组中的物品最多只能选择1个每个组的物品的体积分别为2 0 2^020∗ v [ i ] *v[i]∗v[i]、2 1 2^121∗ v [ i ] *v[i]∗v[i]…2 k 2^k2k∗ v [ i ] *v[i]∗v[i]、C CC∗ v [ i ] *v[i]∗v[i]每个组的物品的价值分别为2 0 2^020∗ w [ i ] *w[i]∗w[i]、2 1 2^121∗ w [ i ] *w[i]∗w[i]…2 k 2^k2k∗ w [ i ] *w[i]∗w[i]、C CC∗ w [ i ] *w[i]∗w[i]组数为N ∗ l o g S N*logSN∗logS这样就将多重背包看成01背包求解代码1(二维数组)#includebits/stdc.husingnamespacestd;constintN1100010,M200010;//NN*logSintn,V,cnt,v[N],w[N],f[N][M];intmain(){cinnV;for(inti1;in;i){inta,b,s;cinabs;intk1;while(ks){cnt;v[cnt]a*k;w[cnt]b*k;s-k;k*2;}if(s){cnt;v[cnt]a*s;w[cnt]b*s;}}ncnt;for(inti1;in;i)for(intj0;jV;j){f[i][j]f[i-1][j];if(v[i]j)f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);}coutf[n][V];return0;}代码2(一维数组)#includebits/stdc.husingnamespacestd;constintN1100010,M200010;//NN*logSintn,V,cnt,v[N],w[N],f[M];intmain(){cinnV;for(inti1;in;i){inta,b,s;cinabs;intk1;while(ks){cnt;v[cnt]a*k;w[cnt]b*k;s-k;k*2;}if(s){cnt;v[cnt]a*s;w[cnt]b*s;}}ncnt;for(inti1;in;i)for(intjV;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);coutf[V];return0;}结果