0-1背包问题及变种

超、凢脫俗 2022-08-12 00:28 93阅读 0赞

**0-1背包问题：**

有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题的特点是：每种物品只有一件，可以选择放或者不放。

**算法基本思想：**

利用动态规划思想 ，子问题为：f\[i\]\[v\]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

其状态转移方程是：f\[i\]\[v\]=max\{f\[i-1\]\[v\],f\[i-1\]\[v-c\[i\]\]+w\[i\]\} //**这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。**

解释一下上面的方程：“将前i件物品放入容量为v的背包中”这个子问题，如果只考虑第i件物品放或者不放，那么就可以转化为只涉及前i-1件物品的问题，即1、如果不放第i件物品，则问题转化为“前i-1件物品放入容量为v的背包中”；2、如果放第i件物品，则问题转化为“前i-1件物品放入剩下的容量为v-c\[i\]的背包中”(此时能获得的最大价值就是f \[i-1\]\[v-c\[i\]\]再加上通过放入第i件物品获得的价值w\[i\])。则f\[i\]\[v\]的值就是1、2中最大的那个值。

（注意：f\[i\]\[v\]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并一定是f\[N\] \[V\]，不一定是唯一的最大值，也可以是f\[N\]\[0..V\]的最大值。

以上概念和算法基本思想来源于blog：http://www.cnblogs.com/fly1988happy/archive/2011/12/13/2285377.html

**以下为算法代码：是个不断优化的过程。首先(1)给出了递归和迭代的思想，(2)然后对迭代的算法代码进行空间优化。(3)然后给出了该问题的变种：恰好装满背包和完全背包问题。**

**(1)递归方法：**

// 0-1 背包问题递归方法  回溯求最佳解
    int packageRecursion(int c, int n)
    {
    	if(n == N) 
    		return (c < weight[n])? 0 : value[n];
    	if(c < weight[n]) 
    		return packageRecursion(c, n+1);
    	return max(packageRecursion(c, n+1), packageRecursion(c - weight[n], n+1) + value[n]);
    }

**(2)迭代方法：**

//  0-1 背包问题迭代方法 
    void packageIteraction()
    {
    	int **F;
    	F = new int*[N+1];   // 申请内存空间
    	int i;
    	for(i = 0; i < N+1; i++)
    	{
    		F[i] = new int [C+1];
    		
    	}
    
    	int j;
    	for(i = 0 ; i < N+1; i++)
    	{
    		for(j = 0; j < C+1; j++)
    		{
    			F[i][j] = 0;              // 初始化
    		}
    	}
    
    	// 正好装满背包 加上这几行
    	/*for(i = 0 ; i < N+1; i++)
    	{
    		for(j = 1; j < C+1; j++)
    		{
    			F[i][j] = min;             
    		}
    	}*/
    
    
    	for(i = 1; i < N+1; i++)
    	{
    		for(j = weight[i]; j < C+1; j++)
    		{
    			F[i][j] = F[i-1][j] > (F[i-1][j-weight[i]]+value[i])? F[i-1][j] : (F[i-1][j-weight[i]]+value[i]);
    		}
    	}
    	if(F[N][C] > 0)
    	{
    		cout << "the opt value:" << F[N][C] << endl; 
    		j = C;                //  回溯 遍历出所选择的节点
    		for(i = N; i >= 1; i--)
    		{
    			if(F[i][j] == (F[i-1][j-weight[i]]+value[i]))
    			{
    				cout << i << "weight=: " << weight[i] << " value=: "<< value[i] << endl;
    				j = j - weight[i];
    			}
    		}
    	}
    	else{
    		cout << "not finde the opt value" << endl;
    	}
    	
    	for(i = 0; i < N+1; i++)     // 释放内存空间
    	{
    		delete[] F[i];
    	}
    	delete[] F;
    
    }

**（3）迭代方法优化空间复杂度：**

以上迭代方法的时间复杂度和空间复杂度都是O(N\*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。此时的做法是用F\[V\]来存储当前获得的价值的最大值，第二个for循环反向遍历。

//  将j=V:weight[i] 只用一维数组保存就可以了，降低了空间复杂度
    void packageIteractionOpt()
    {
    
    	int *F;
    	F = new int[C+1];   // 申请内存空间
    	int i;
    	for(i = 0; i < C+1; i++)
    		F[i] = 0;
    
    	// 正好装满背包 加上这句
    	/*for(i = 1; i < C+1; i++)      
    		F[i] = min; */
    
    	for(i = 1; i < N+1; i++)
    	{
    		for(int j= C; j >= weight[i]; j--)
    		{
    			F[j] = F[j] > (F[j-weight[i]]+value[i])? F[j] : (F[j-weight[i]]+value[i]);
    		}
    	}
    	cout << F[C] << endl;
    
    	delete []F;     // 释放内存空间
    }

注意：上面要从后往前遍历，前面的都是上一次的结果，如果从前往后遍历，前面的是这次的结果。

Main函数代码：

int main()
    {
    	cin >> C >> N;
    	weight = new int[N+1];
    	value = new int[N+1];
    	value[0] = 0;
    	weight[0] = 0;
    	int i;
    	for(i = 1; i <= N; i++)
    		cin >> value[i] >> weight[i];
    	
    	//cout << packageRecursion(C, 1) << endl;   // 递归方法
    	//packageIteraction();
    	packageIteractionOpt();        // 在同等条件下，降低了空间复杂度
    
    	delete []weight;
    	delete []value;
    	//cout << int(0x80000000) << endl;     // int 中最小值
    	//cout << int(0xfffffffff) << endl; ;            // int中-1
    
    	return 0;
    }

输出结果：

![SouthEast][]

**(4)变种**

**1：恰好装满背包**

在初始化时除了f\[0\]为0其它f\[1..V\]均设为-∞，这样就可以保证最终得到的f\[V\]是一种恰好装满背包的最优解，即背包中存有的价值，不是背包的容量。如果不能恰好满足背包容量，即不能得到f\[V\]的最优值，则此时f\[V\]=-∞，这样就能表示没有找到恰好满足背包容量的最优值。

以上代码中可以将注释的部分加上就可以了。其中int类型中最小值为0x80000000.

**2：完全背包**

此问题来源于hihoCoder中：链接，即将背包只能兑换一次或者不兑换改为可以兑换无数次

/*完全背包问题 http://hihocoder.com/contest/hiho7/problem/1 */
    #include <iostream>
    #include <memory.h>    //A题时候使用memset需要添加这个库函数
    using namespace std;
    int main()
    {
    	int N, M;
    	while(cin >> N >> M)
    	{
    		int need, value;
    		int *F = new int[M+1];
    
    		int i, j;
    		memset(F, 0, sizeof(int)*(M+1));
    		//for(i = 0; i < M+1; i++)
    			//F[i] = 0;
    
    		for(i = 1; i < N+1; i++)
    		{
    			cin >> need >> value;
    			for(j = need; j<=M; j++)
    			{
    				F[j] = F[j] > (F[j-need]+value)?F[j]:(F[j-need]+value);
    			}	
    		}
    		
    		// 错误代码
    		/*
    		如样例 2 10 2 3 3 5
    		*/
    		/*int k;
    		for(i = 1; i < N+1; i++)
    		{
    			cin >> need >> value;
    			for(j = M; j>=need; j--)
    			{
    				if(need == 0) k = 0;
    				else k = j/need;   //  
    				F[j] = F[j] > (F[j-k*need]+k*value)?F[j]:(F[j-k*need]+k*value);  
    			}
    		}*/
    		cout << F[M] << endl;
    		delete []F;
    	}
    }
    
    // 测试输入
    /*5 1000
    144 990
    487 436
    210 673
    567 58
    1056 897*/
    
    // 输出
    // 5940

参考文献

1： http://www.cnblogs.com/fly1988happy/archive/2011/12/13/2285377.html

2：http://www.cnblogs.com/findumars/archive/2012/01/28/2330647.html

3：http://blog.csdn.net/shaopengfei/article/details/1473020

作者：小村长  出处：http://blog.csdn.net/lu597203933 欢迎转载或分享，但请务必声明文章出处。 （新浪微博：小村长zack, 欢迎交流！）

附腾讯笔试题

“背包题目”的基本描述是：有一个背包，能盛放的物品总重量为S,设有N件物品，其重量分别为w1，w2，…，wn，希望从N件物品中选择若干物品，所选物品的重量之和恰能放进该背包，即所选物品的重量之和即是S。递归和非递归解法都能求得“背包题目”的一组解，试写出“背包题目”的非递归解法

分析：

(1)递归解法直接用回溯就可以了，我们看代码：

// 回溯
    	void backTracking(int depth, int maxDepth, vector<int> temp, vector<int> vec, const int &S){
    		if(depth == maxDepth){    // 递归结束
    			int sum = 0;
    			vector<int> tmp;
    			for(int i = 0; i < maxDepth; i++){
    				if(temp[i] == 1){
    					sum += vec[i];
    					tmp.push_back(i);
    				}
    			}
    			if(sum == S)result.push_back(tmp);
    			return;
    		}
    
    		backTracking(depth+1, maxDepth, temp, vec, S);    // 没有取depth的元素时的递归
    		temp[depth]=1;
    		backTracking(depth+1, maxDepth, temp, vec, S);   // 取depth的元素时的递归
    	}

(2)非递归求出所有的解，我们可以采用位操作：

// 找出所有的解
    	void package(vector<int> vec, int S){
    		int n = vec.size();
    		int s = 1 << n;
    		for(int i = 1; i < s; i++){
    			int sum = 0;
    			vector<int> temp;
    			for(int j = 0; j < n; j++){
    				if((i & (1<<j)) != 0){ 
    					sum += vec[j];
    					temp.push_back(j);
    				}
    			}
    			if(sum == S) result.push_back(temp);
    		}
    	}

但时间复杂度较高为O(s\*2^n)

动态规划求一组解，我们用f\[i\]\[j\]用来表示前i件物品随意选择一些物品能够恰好装满容量为j的背包的可行性=1，不可行则为0；如果j < v\[i\]:f\[i\]\[j\] = f\[i-1\]\[j\] ，表示第i个物品的重量已经超过最大重量j了，则结果变为了前i-1件物品能否恰好装入容量为j的背包的可行性即等于f\[i-1\]\[j\]；

如果j>=v\[i\]，此时就可以选择装或者不装第i件物品了，如果装入，则它的可行性就变为了前i-1前物品是否能恰好装入j-vec\[i\]容量的背包中可行性了；选择不装，则它的可行性变为了前i-1物品能否恰好装入容量为j的背包中可行性了，两者有一个可行，表明前i件物品就能恰好装入容量为j的背包中。f\[i\]\[j\] = f\[i-1\]\[j\]||f\[i-1\]\[j-vec\[i\]\]

初始化：f\[i\]\[0\]=1(i=0,1,2,,..n) 其它的f\[i\]\[j\]都等于0

找出最终的一组解，用回溯就可以了。如果存在可行解，那么f\[n\]\[S\]一定为1

代码：

// f[i][j]用来表示前i件物品随意选择一些物品能够恰好装满j的可行性=1，不可行则为0，
    	// 如果j < v[i]:f[i][j] = f[i-1][j]  表示肯定不能取第i件物品了，那么就变为i-1件能否恰好装入容量为j的背包的可行性了。
    	//  否则，f[i][j] = f[i-1][j]||f[i-1][j-v[i]]  表示装第i件物品,问题变为前i-1件物品是否能恰好装进j-vec[i]中的可行性或者不装第i件物品，则问题变为前i-1件能否恰好装入容量为j的背包的可行性f[i-1][j]，相或即为结果
    	// 初始化，除了f[0][j]为1，其余全部0
    
    	// 最终的结果f[n][S]为1表明存在一组解使得n解物品肯定能恰好装满容量为j的背包
    
    	void packageInteration(vector<int> vec, int S){
    
    		int n = vec.size();
    		int **f = new int*[n+1];
    		for(int i = 0; i < n+1; i++){
    			f[i] = new int[S+1];
    			memset(f[i], 0, sizeof(f[i])*(S+1));
    		}
    		for(int i = 0; i < n+1; i++)
    				f[i][0] = 1;   // 初始化
    
    		for(int i = 1; i < n+1; i++){
    			for(int j = 1; j < S+1; j++){
    				if(j >= vec[i-1])f[i][j] = (f[i-1][j] || f[i-1][j-vec[i-1]]);
    				else f[i][j] = f[i-1][j];
    			}
    		}
    
    
    		for(int i = 1; i < n+1; i++){
    			for(int j = 1; j < S+1; j++){
    				cout << f[i][j] << " ";
    			}
    			cout << endl;
    		}
    
    		// 回溯求结果
    		int j = S;
    		for(int i = n; i > 0; i--){
    			if(j >= vec[i-1]){
    				if(f[i][j-vec[i-1]] == 1){   // 为0 表示可行
    					res.push_back(i);
    					j = j - vec[i-1];
    				}
    			}
    		}
    	
    		
    	}

[SouthEast]: /images/20220810/9e77183b0d08464a997ae52c34eeaf47.png