多重背包经典解法

给定背包容量 m ，物品种数 n ，每个物品的体积 a i a_{i} ai​ ，价值 b i b_{i} bi​ ，个数 c i c_{i} ci​。

求背包能装下的最大价值和，且输出任意可行方案。

这是经典的多重背包问题，可以有多种解法。

1. 01背包解法

   按每种物品的个数 c i c_{i} ci​ 将物品拆成 c i c_{i} ci​ 个物品然后做全部拆完后的物品的 01 背包，很明显复杂度是 O ( n m ∑ c i ) O(nm\sum{c_{i}}) O(nm∑ci​) 的。
   

   
   

   先解释以下输出方案的问题：以二维数组来计算，在计算完后，找到第 n 个物品最大价值的位置 f [ n ] [ p ] f[n][p] f[n][p] ，此时比较它和 f [ n − 1 ] [ p ] f[n-1][p] f[n−1][p] 的值，若是不相等则说明在当前容量时取了第 n 个物品，输出然后减去容量即可，依次类推。
   

   
   

   记得不要拿超过 c i c_{i} ci​ 次 i 物品。
   

   
   

   code

   #pragma GCC optimize("Ofast")
   #pragma GCC optimize("unroll-loops")
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   
   using namespace std;
   using ll=long long;
   using P=pair<int,int>;
   const ll inf=1e18;
   
   void solve()
   {
   	int n,m; cin>>n>>m;
   	vector<int>a(n+1),b(n+1),c(n+1);
   
   	for(int i=1;i<=n;i++)cin>>a[i];
   	for(int i=1;i<=n;i++)cin>>b[i];
   	for(int i=1;i<=n;i++)cin>>c[i];
   	vector<vector<int>>f(n+1,vector<int>(m+1));
   
   	for(int i=1;i<=n;i++)
   	{
   		f[i]=f[i-1];
   		for(int j=1;j<=c[i];j++)
   		{
   			for(int k=m;k>=a[i];k--)
   			{
   				f[i][k]=max(f[i][k],f[i][k-a[i]]+b[i]);
   			}
   		}
   	}
   
   	int p=max_element(f[n].begin(),f[n].end())-f[n].begin();
   
   	cout<<f[n][p]<<"\n";
   	for(int i=n;i>=1;i--)
   	{
   		while(f[i][p]>f[i-1][p]&&c[i])
   		{
   			cout<<i<<" ";
   			p-=a[i],c[i]--;
   		}
   	}
   		
   }
   
   int main()
   {
   	ios::sync_with_stdio(false);
   	cin.tie(0); cout.tie(0);
   	int t=1; //cin>>t;
   	while(t--)solve();
   	return 0;
   } 
   

2. 二进制拆分法

   从1 可知，对每个物品循环多次的目的是将其转化为 c i c_{i} ci​ 物品，可以采用将每个物品的循环次数按二进制位去拆分，将其表达成 2 0 , 2 1 . . . 2 k , m − ∑ i = 0 k 2 i 2^0,2^1...2^k,m-\sum_{i=0}^{k}2^i 20,21...2k,m−∑i=0k​2i， 一共有 log 个物品，从 1 到 c i c_{i} ci​ 的物品个数均可以通过使用其中的某一子集拼凑而成，因此只需要将第 i 个物品拆成 log 个物品去按方法一的方式计算即可。
   

   
   

   总复杂度是 O ( n m ∑ l o g ( c i ) ) O(nm\sum{log(c_{i})}) O(nm∑log(ci​)) 。
   

   
   

   code

   #pragma GCC optimize("Ofast")
   #pragma GCC optimize("unroll-loops")
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   
   using namespace std;
   using ll=long long;
   using P=pair<int,int>;
   const ll inf=1e18;
   
   void solve()
   {
   	int n,m; cin>>n>>m;
   	vector<int>a(n+1),b(n+1),c(n+1);
   
   	for(int i=1;i<=n;i++)cin>>a[i];
   	for(int i=1;i<=n;i++)cin>>b[i];
   	for(int i=1;i<=n;i++)cin>>c[i];
   	vector<vector<int>>f(n+1,vector<int>(m+1));
   
   	for(int i=1;i<=n;i++)
   	{
   		f[i]=f[i-1];
   		int p=c[i];
   		for(int j=1;j<=p;p-=j,j<<=1)
   		{
   			for(int k=m;k>=j*a[i];k--)
   			{
   				f[i][k]=max(f[i][k],f[i][k-j*a[i]]+j*b[i]);
   			}
   		}
   		if(p)
   		{
   			for(int k=m;k>=p*a[i];k--)
   			{
   				f[i][k]=max(f[i][k],f[i][k-p*a[i]]+p*b[i]);
   			}	
   		}
   	}
   
   	int p=max_element(f[n].begin(),f[n].end())-f[n].begin();
   
   	cout<<f[n][p]<<"\n";
   	for(int i=n;i>=1;i--)
   	{
   		while(f[i][p]>f[i-1][p]&&c[i])
   		{
   			cout<<i<<" ";
   			p-=a[i],c[i]--;
   		}
   	}
   		
   }
   
   int main()
   {
   	ios::sync_with_stdio(false);
   	cin.tie(0); cout.tie(0);
   	int t=1; //cin>>t;
   	while(t--)solve();
   	return 0;
   } 
   

3. 单调队列优化

   考虑当前枚举的是物品i，对于容量j而言，可以继承的只有 j − a i , j − 2 a i . . . j − x ∗ a i ( x < = c i & & j − x ∗ a i > = 0 ) j-a_{i},j-2a_{i}...j-x*a_{i}(x<=c_{i}\&\&j-x*a_{i}>=0) j−ai​,j−2ai​...j−x∗ai​(x<=ci​&&j−x∗ai​>=0)，也就是说对于在模 a i a_{i} ai​ 的余数集下，不同余数集间互不干扰，因此可以将余数集进行分开枚举。
   

   
   

   对于同一个余数集， f [ i ] [ j ] = m a x { f [ i − 1 ] [ j − x ∗ a i ] + x ∗ b i } , x < = c i f[i][j]=max\{f[i-1][j-x*a_{i}]+x*b_{i}\},x<=c_{i} f[i][j]=max{f[i−1][j−x∗ai​]+x∗bi​},x<=ci​ ，可以使用单调队列来维护，在每次计算出 f [ i ] [ j ] f[i][j] f[i][j] 之后，将向队列中插入 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] ，在插入前需要判断当前尾端的数据 f [ i − 1 ] [ k ] + ( j − k ) / a i ∗ b i ( j % a i = = k % a i ) f[i-1][k]+(j-k)/a_{i}*b_{i}(j\%a_{i}==k\%a_{i}) f[i−1][k]+(j−k)/ai​∗bi​(j%ai​==k%ai​) 是否比 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] 更大，若不是，则 f [ i − 1 ] [ k ] f[i-1][k] f[i−1][k] 这个点并不比 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] 优，因此可以从尾端d出队列。
   

   
   

   对以上 *** 作多次执行，直到尾端的点比当前点优，才插入加入当前点。
   

   
   

   这样 *** 作下来队列内的点是逐渐递减的（并不指数值大小逐渐递减，而是对于容量 j 时，满足 f [ i − 1 ] [ x ] + ( j − x ) / a i ∗ b i > = f [ i − 1 ] [ y ] + ( j − y ) / a i ∗ b i f[i-1][x]+(j-x)/a_{i}*b_{i}>=f[i-1][y]+(j-y)/a_{i}*b_{i} f[i−1][x]+(j−x)/ai​∗bi​>=f[i−1][y]+(j−y)/ai​∗bi​ ，其中 x < y xx<y）。
   

   
   

   因此每个 f [ i ] [ j ] f[i][j] f[i][j] 的答案即为队首 f [ i − 1 ] [ t o p ] + ( j − t o p ) / a i ∗ b i f[i-1][top]+(j-top)/a_{i}*b_{i} f[i−1][top]+(j−top)/ai​∗bi​。
   

   
   

   需要在每次取队首为答案前，对队首与当前容量 j 的值进行判定，若是超过限制个数范围则需从队首d出，直到满足情况，则队首就是答案。
   

   
   

   以上队列为双端队列，首尾均可进行d出插入 *** 作。
   

   
   

   对于空间可以将物品这一维优化掉，每次求前只需要用 g = f g=f g=f 保存上一次结果，然后在 g 的基础上更新 f 即可。
   

   
   

   考虑最后的单调队列的优化，对于每个物品会分为多个余数集，但所有的容积就只会被计算一次，而且对于每个物品的入队出队的情况而言，只会最多插入 m 次，d出 m 次。
   

   
   

   取最大值则是的 O ( 1 ) O(1) O(1)。
   

   
   

   则总的复杂度为 O ( n m ) O(nm) O(nm)。
   

   
   

   
   code

   #pragma GCC optimize("Ofast")
   #pragma GCC optimize("unroll-loops")
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   #include
   
   using namespace std;
   using ll=long long;
   using P=pair<int,int>;
   const ll inf=1e18;
   
   void solve()
   {
   	int n,m; cin>>n>>m;
   	vector<int>a(n+1),b(n+1),c(n+1);
   
   	for(int i=1;i<=n;i++)cin>>a[i];
   	for(int i=1;i<=n;i++)cin>>b[i];
   	for(int i=1;i<=n;i++)cin>>c[i];
   	vector<vector<int>>f(n+1,vector<int>(m+1));
   
   	for(int i=1;i<=n;i++)
   	{
   		f[i]=f[i-1];
   		for(int j=0;j<a[i];j++)
   		{
   			deque<int>dq;
   			for(int k=j;k<=m;k+=a[i])
   			{
   				while(dq.size()&&(k-dq.front())/a[i]>c[i])
   				{
   					dq.pop_front();
   				}
   				if(dq.size())
   				{
   					f[i][k]=max(f[i][k],f[i-1][dq.front()]+(k-dq.front())/a[i]*b[i]);
   				}
   				while(dq.size()&&f[i-1][dq.back()]+(k-dq.back())/a[i]*b[i]<f[i-1][k])
   				{
   					dq.pop_back();
   				}
   				dq.push_back(k);
   			}	
   		}
   	}
   
   	int p=max_element(f[n].begin(),f[n].end())-f[n].begin();
   
   	cout<<f[n][p]<<"\n";
   	for(int i=n;i>=1;i--)
   	{
   		while(f[i][p]>f[i-1][p]&&c[i])
   		{
   			cout<<i<<" ";
   			p-=a[i],c[i]--;
   		}
   	}
   		
   }
   
   int main()
   {
   	ios::sync_with_stdio(false);
   	cin.tie(0); cout.tie(0);
   	int t=1; //cin>>t;
   	while(t--)solve();
   	return 0;
   } 
   

   以上代码未经验证，不能保证正确率。