企业官网建设流程全解析

题目：5. 多重背包问题 II

题目描述

有N NN种物品和一个容量是V VV的背包。

第 i 种物品最多有s i s_isi​件，每件体积是v i v_ivi​，价值是w i w_iwi​。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N NN，V VV，用空格隔开，分别表示物品种数和背包容积。

接下来有N NN行，每行三个整数v i v_ivi​,w i w_iwi​,s i s_isi​，用空格隔开，分别表示第i ii种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N ≤ 1000 0 < N ≤ 10000<N≤1000

0 < V ≤ 2000 0 < V ≤ 20000<V≤2000

0 < v i , w i , s i ≤ 2000 0 < v_i, w_i, s_i ≤ 20000<vi​,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 s=2^0s=20+2 1 2^121+2 2 2^222+ … +2 k 2^k2k+C 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(二维数组)

#include<bits/stdc++.h>usingnamespacestd;constintN=11000+10,M=2000+10;//N=N*logSintn,V,cnt,v[N],w[N],f[N][M];intmain(){cin>>n>>V;for(inti=1;i<=n;i++){inta,b,s;cin>>a>>b>>s;intk=1;while(k<=s){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s){cnt++;v[cnt]=a*s;w[cnt]=b*s;}}n=cnt;for(inti=1;i<=n;i++)for(intj=0;j<=V;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]);}cout<<f[n][V];return0;}

代码2(一维数组)

#include<bits/stdc++.h>usingnamespacestd;constintN=11000+10,M=2000+10;//N=N*logSintn,V,cnt,v[N],w[N],f[M];intmain(){cin>>n>>V;for(inti=1;i<=n;i++){inta,b,s;cin>>a>>b>>s;intk=1;while(k<=s){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s){cnt++;v[cnt]=a*s;w[cnt]=b*s;}}n=cnt;for(inti=1;i<=n;i++)for(intj=V;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[V];return0;}

结果