多重背包问题

本文包含的内容：

<1> 问题描述

<2> 基本思路（和完全背包类似）

<3> 转换为01背包问题求解（直接利用01背包）

---------------------------------------------

1、问题描述

 

已知:有一个容量为V的背包和N件物品，第i件物品最多有Num[i]件，每件物品的重量是weight[i]，收益是cost[i]。

问题:在不超过背包容量的情况下，最多能获得多少价值或收益

举例：物品个数N = 3，背包容量为V = 8，则背包可以装下的最大价值为64.

----------------------------------------------

 

2、基本思路（直接扩展01背包的方程）

由于本问题和完全背包很类似，这里直接给出方程。

 

[cpp] view plaincopyprint?
  1. 状态转移方程：  
  2.   
  3. f[i][v]:表示前i件物品放入重量为v的背包获得的最大收益  
  4. f[i][v] = max(f[i][v],f[i - 1][V - k * Weight[i]] + k * Value[i]);  
  5. 其中0 <= k <= min(Num[i],V/Weight[i]);//这里和完全背包不同。   
  6. 边界条件  
  7. f[i][0] = 0;  
  8. f[v][0] = 0;  
状态转移方程：

f[i][v]:表示前i件物品放入重量为v的背包获得的最大收益
f[i][v] = max(f[i][v],f[i - 1][V - k * Weight[i]] + k * Value[i]);
其中0 <= k <= min(Num[i],V/Weight[i]);//这里和完全背包不同。
边界条件
f[i][0] = 0;
f[v][0] = 0;

代码：

 

[cpp] view plaincopyprint?
  1. #include <iostream>   
  2. using namespace std;  
  3. const int N = 3;//物品个数   
  4. const int V = 8;//背包容量   
  5. int Weight[N + 1] = {0,1,2,2};  
  6. int Value[N + 1] = {0,6,10,20};  
  7. int Num[N + 1] = {0,10,5,2};  
  8. int f[N + 1][V + 1] = {0};  
  9. /* 
  10. f[i][v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 
  11. f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Weight[i]] + K * Value[i]);其中1 <= k <= min(Num[i],V/Weight[i]) 
  12. //初始化 
  13. f[i][0] = 0; 
  14. f[0][v] = 0; 
  15. */  
  16. int MultiKnapsack()  
  17. {  
  18.     int nCount = 0;  
  19.     //初始化   
  20.     for (int i = 0;i <= N;i++)  
  21.     {  
  22.         f[i][0] = 0;  
  23.     }  
  24.     for (int v = 0;v <= V;v++)  
  25.     {  
  26.         f[0][v] = 0;  
  27.     }  
  28.     //递推   
  29.     for (int i = 1;i <= N;i++)  
  30.     {  
  31.         for (int v = Weight[i];v <= V;v++)  
  32.         {  
  33.             f[i][v] = 0;  
  34.             nCount = min(Num[i],v/Weight[i]);//是当前背包容量v，而不是背包的总容量   
  35.             for (int k = 0;k <= nCount;k++)  
  36.             {  
  37.                 f[i][v] = max(f[i][v],f[i - 1][v - k * Weight[i]] + k * Value[i]);  
  38.             }  
  39.         }  
  40.     }  
  41.     return f[N][V];  
  42. }  
  43. int main()  
  44. {  
  45.     cout<<MultiKnapsack()<<endl;  
  46.     system("pause");  
  47.     return 1;  
  48. }  
#include <iostream>
using namespace std;
const int N = 3;//物品个数
const int V = 8;//背包容量
int Weight[N + 1] = {0,1,2,2};
int Value[N + 1] = {0,6,10,20};
int Num[N + 1] = {0,10,5,2};
int f[N + 1][V + 1] = {0};
/*
f[i][v]:表示把前i件物品放入容量为v的背包中获得的最大收益。
f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Weight[i]] + K * Value[i]);其中1 <= k <= min(Num[i],V/Weight[i])
//初始化
f[i][0] = 0;
f[0][v] = 0;
*/
int MultiKnapsack()
{
	int nCount = 0;
	//初始化
	for (int i = 0;i <= N;i++)
	{
		f[i][0] = 0;
	}
	for (int v = 0;v <= V;v++)
	{
		f[0][v] = 0;
	}
	//递推
	for (int i = 1;i <= N;i++)
	{
		for (int v = Weight[i];v <= V;v++)
		{
			f[i][v] = 0;
			nCount = min(Num[i],v/Weight[i]);//是当前背包容量v，而不是背包的总容量
			for (int k = 0;k <= nCount;k++)
			{
				f[i][v] = max(f[i][v],f[i - 1][v - k * Weight[i]] + k * Value[i]);
			}
		}
	}
	return f[N][V];
}
int main()
{
	cout<<MultiKnapsack()<<endl;
	system("pause");
	return 1;
}

复杂度分析：

程序需要求解N*V个状态，每一个状态需要的时间为O（v/Weight[i]），总的复杂度为O(NV*Σ(V/Weight[i]))。

3、转换为01背包问题求解（直接利用01背包）

思路 1、直接对每一件物品进行拆分成min（Num[i],V/Weight[i]）件，之后在拆分后的集合上进行01背包的求解。

时间复杂度：和基本思路一样，没有降低。

思路 2、采用二进制拆分的思想。对每i件物品，拆分的策略为：新拆分的物品的重量等于1件,2件,4件,..,(2^(k - 1)),Num[i] - (2^(k - 1))件，其中k 是满足Num[i] - 2^k + 1 > 0 的最大整数。

注意，

（1）最后一个物品的件数的求法和前面不同，其直接等于 该物品的最大件数 - 前面已经分配之和。

（2）分成的这几件物品的系数和为

Num[i]，表明第i种物品取的件数不能多于Num[i]。

 

举例：某物品为13件，则其可以分成四件物品，其系数为1,2,4,6.这里k = 3。

 

当然，这里使用二进制的前提还是使用二进制拆分能

保证对于0,,,Num[i]间的每一个整数，均可以用若干个系数的和表示。

具体使用时，有一个小优化，即：

我们不对所有的物品进行拆分，因此物品一旦拆分，其物品个数肯定增加，那么复杂度肯定上去。

 

此时，我们可以选择性地对物品进行拆分：

 

（1）如果第i个物品的重量Weight[i] * 物品的个数Num[i] >= 背包总重量V，可以不用拆分。

 

（2）如果第i个物品的重量Weight[i] * 物品的个数Num[i] < 背包总重量V，可以不用拆分。

 

其实，拆不拆分，就看该物品能不能满足完全背包的条件。即，看该物品能不能无限量供应。

 

解释：为啥满足Weight[i] * 物品的个数Num[i] >= 背包总重量V的物品可以不用拆分?

 

此时，满足该条件时，此物品原则上是无限供应，直到背包放不下为止。

 

最终，对于不需要拆分的物品，可以看出完全背包的情况，调用处理完全背包物品的函数。对于需要拆分的物品，可以看出01背包的情况，调用处理01背包物品的函数。

 

这样，由于不对满足完全背包的物品进行拆分，此时物品个数就没有对所有物品拆分时的物品个数多，即程序中外层循环降低，复杂度也就下去了。

 

伪代码：

 


 

这里：C表示该物品的重量。M表示该物品的个数。V表示背包的最大容量。W表示该物品的收益。

 

代码：

 

 

 

[cpp] view plaincopyprint?
  1. #include <iostream>   
  2. using namespace std;  
  3.   
  4. const int N = 3;//物品个数   
  5. const int V = 8;//背包容量   
  6. int Weight[N + 1] = {0,1,2,2};  
  7. int Value[N + 1] = {0,6,10,20};  
  8. int Num[N + 1] = {0,10,5,2};  
  9.   
  10. int f[V + 1] = {0};  
  11. /* 
  12. f[v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 
  13. f[v] = max(f[v],f[v - Weight[i]] + Value[i]); 
  14. v的为逆序 
  15. */  
  16. void ZeroOnePack(int nWeight,int nValue)  
  17. {  
  18.     for (int v = V;v >= nWeight;v--)  
  19.     {  
  20.         f[v] = max(f[v],f[v - nWeight] + nValue);  
  21.     }  
  22. }  
  23.   
  24. /* 
  25. f[v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 
  26. f[v] = max(f[v],f[v - Weight[i]] + Value[i]); 
  27. v的为增序 
  28. */  
  29. void CompletePack(int nWeight,int nValue)  
  30. {  
  31.     for (int v = nWeight;v <= V;v++)  
  32.     {  
  33.         f[v] = max(f[v],f[v - nWeight] + nValue);  
  34.     }  
  35. }  
  36.   
  37. int MultiKnapsack()  
  38. {  
  39.     int k = 1;  
  40.     int nCount = 0;  
  41.     for (int i = 1;i <= N;i++)  
  42.     {  
  43.         if (Weight[i] * Num[i] >= V)  
  44.         {  
  45.             //完全背包:该类物品原则上是无限供应，   
  46.             //此时满足条件Weight[i] * Num[i] >= V时，   
  47.             //表示无限量供应，直到背包放不下为止.   
  48.             CompletePack(Weight[i],Value[i]);  
  49.         }  
  50.         else  
  51.         {  
  52.             k = 1;  
  53.             nCount = Num[i];  
  54.             while(k <= nCount)  
  55.             {  
  56.                 ZeroOnePack(k * Weight[i],k * Value[i]);  
  57.                 nCount -= k;  
  58.                 k *= 2;  
  59.             }  
  60.             ZeroOnePack(nCount * Weight[i],nCount * Value[i]);  
  61.         }  
  62.     }  
  63.     return f[V];  
  64. }  
  65.   
  66. int main()  
  67. {  
  68.     cout<<MultiKnapsack()<<endl;  
  69.     system("pause");  
  70.     return 1;  
  71. }  

 

 

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/13224ACMer/p/4397248.html