0-1背包问题

女爷i 2022-08-11 07:30 144阅读 0赞

**问题描述：有N个物品和一个最大可以承受重量为c的背包。每个物品的重量为\{W1,W2,W3,.....,Wn\}；**

**每个物品的价值为\{p1,p2,....pn\}。现求将哪些物品放入背包中可以获得最大的价值。**

**思路：**

**假设总共有n个产品，每个物品的重量为m\[i\] (0=<i<=n);**

**每个物品的价值为p\[n\] (0=<i<=n)；**

**m(i,j)表示选择了第i个产品时的价值，j表示背包剩余可以承受的最大重量。**

**如果要求解背包中放入哪些产品可以获得最大的价值，**

**我们将这个问题看成n步操作，每步操作代表****我们是否将第i(0=<i<=n)个产品放入背包中。**

**用f(i, j)表示选择第i个物品时可以获取的最大价值，j表示对应的背包剩余可以承受的最大重量。**

**f(i+1, j)表示选择第i+1个物品时的最大可以获取的价值。**

**f(i,j)步操作时，要么选择第i个产品，要么不选择第i个产品****。**

**当选取了这个产品时，则其价值为f(i+1)+p\[i\]，****则背包剩余可以容纳的重量为j-w\[i\]；**

**如果没有选取这个产品，则其价值和f(i+1)相同，****背包剩余可以容纳的重量不变，仍为j。**

**当然，如果第i个产品的重量大于背包剩余可以承受的最大重量时，**

**则肯定不能选取这个产品。**

**总结来说,**即得到下面的公式：

**if(w\[i\]  > j)//当w\[i\]大于背包可以容纳的重量时，则必定不选取第i个产品。**

**f(i, j) = f(i+1 , j);**

**else //否则,f(i,j)为选取和不选取两种情况下的较大值。**

**f(i, j) = max( f(i+1, j-w\[i\]) + p\[i\],  f(i+1, j))**

**这使用递归的思想很好解决，**

**代码如下：**

#include <stdio.h>
    
    #define NUM 6
    
    #define MAX(a,b) (a)>(b)?(a):(b)
    
    int w[NUM] = {15,17,20,12,9,14};
    int p[NUM] = {32,37,46,26,21,30};
    int c = 60;//背包最大的容量。
    
    //id代表第i个元素，left表示背包剩余可以承受的重量。
    int pack(int id, int left){
    	if(id >= NUM)
    		return 0;
    	if(w[id] > left){
    		return pack(id+1, left);
    	}else{
    		return MAX(pack(id+1, left-w[id])+p[id], pack(id+1, left));
    	}
    }
    
    void main(int argc, char **argv)
    {
    	int max = pack(0, c);
    	printf("max=%d\n",max);
    }

若使用非递归的方法来解决这个问题，则需要开辟一个空间来记住选择完第i个背包时的最大价值。

具体思路：

开辟一个n\*(c+1)的二维数组m。m\[i\]\[j\]表示选择已经选择了\{0,1,2,..,i-1,i\}个物品，背包的容量为j时，

背包中物品的最大的价值数目。

二维数组的行数为物品的数目，列数为背包最大可以承受的容量+1。

接下来我们用迭代来解决这个问题：

当放入第i个物品的时候，对于背包的每个容量j(0 =< j <= c)而言，其可以装入物品的最大价值为：

如果w\[i\] > j， 则表示第i个物品的重量大于背包的重量，则m\[i\]\[j\]为上一步选取时，背包中物品的最大价值m\[i-1\]\[j\]。

如果w\[i\] < j， 则w\[i\]等于m\[i-1\]\[j-w\[i\]\] + p\[i\] 和m\[i-1\]\[j\]中较大的一个。

所以非递归的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    #define NUM 6
    
    //0-1背包问题。
    void main(int argc, char **argv)
    {
    	int w[NUM] = {15,17,20,12,9,14};//重量
    	int p[NUM] = {32,37,46,26,21,30};//效益
    	int c = 60;
    	int i, j;
    	int m[NUM][61];
    	//初始化。
    	memset(m , 0, sizeof(int)*NUM*c);
    
    		
    	for(i = 0; i < NUM; i++){//对于每个物品，测试它可以放置的最大的重量。
    		for(j = 0; j <= c; j++){
    			if(j < w[i]){
    				if(i >= 1)
    					m[i][j] = m[i-1][j];			
    			}else{
    				if(i >= 1)
    				<span style="white-space:pre">	</span>m[i][j] = (m[i-1][j]>(m[i-1][j-w[i]]+p[i]))?(m[i-1][j]):(m[i-1][j-w[i]]+p[i]);				
    				else 
    					m[i][j] = p[i];				
    			}		
    		}	
    	}
    	
    	printf("max=%d\n",m[NUM-1][c]);//最大的元素放置在m[NUM-1][c]位置上。
    	
    }