首页 > 代码库 > 0-1背包问题——动态规划法

0-1背包问题——动态规划法

问题描述:给定n种物品和一背包。物品i的重量是w[i],其价值为v[i],背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
分析:对于一种物品,要么装入背包,要么不装。所以对于一种物品的装入状态可以取0和1。设物品i的装入状态为xi,xi∈ (0,1),此问题称为0-1背包问题。
数据:物品个数n=5,物品重量w[5]={2,2,6,5,4},物品价值v[5]={6,3,5,4,6},总重量c=10。背包的最大容量为10,那么在设置数组m大小时,可以设行列值为5和10,那么,对于m(i,j)就表示可选物品为i到n且背包容量为j(总重量)时背包中所放物品的最大价值。看下面这个表格即为动态规划法解0-1背包问题的过程:

表格中灰色的为序号:列的1~5表示5个物品,横向的1~10表示背包的容量,绿色的列表示相对应物品的的重量,浅蓝色的一列表示相对应物品的价值。假设新建一个5*10的数组对应图片中的棕色部分,棕色部分即为求解的过程,具体求解过程如下:
图上所示的求解过程是从下往上求解,也就是说先分析第5个物品,最后分析第一个物品。当背包中为空的时候,考虑第5个物品,当背包容量为1, 2, 3的时候这个背包都是装不下物品5的,因为物品5的重量是4,因此对应的当背包容量为1, 3, 3的时候背包里面东西的价值(棕色表格里面的值)也是为0,当背包容量大于等于4的时候背包可以放下物品5,所以背包里面东西的价值就是6(因为这里先只考虑只有一件物品5的时候),到此只有物品5的情况已经分析完毕;
接下来分析同时拥有物品5和物品4的情况,当背包容量为1, 2, 3的时候,背包里面既放不下4物品也放不下5物品,所以背包里面物品的价值为0,当背包容量大于等于4的时候,至少可以放下物品5了,这个时候就要取舍了,到底是将物品5放进去价值大还是将物品4放进去价值大,当背包容量为4的时候,只能放进去物品5,价值为6,当背包容量为5的时候如果选择房屋物品4,那么剩余的背包容量为0,查找背包重量为0的列(在前面步骤已经填充过的部分,这里只填充了第5行第1列的位置),找这一列的最大值为0,所以选择放物品4的时候背包价值最大为4<不放物品4(剩余背包容量为5,查找背包容量5对应的填充过的部分,其最大值为6)时候的6,所以在背包容量为5的时候的最优值是放物品5而不放物品4,一直分析到背包容量为9的时候当选择放入物品4的时候,剩余背包容量为4,再查找背包容量为4时候已经填充过的部分(即最后一行),可以查得最大值为6,所以这个时候选择放入物品4可以获得的最大价值为10。...
中间的过程都是如此,这里再分析一下最后一个物品的放置,背包容量为2的时候,如果放入物品1,获得的价值为6,剩余背包容量为0,剩余背包容量获得的最大价值为0,所以6+0=6为最大价值,如果不放入1物品,剩余背包容量为2,剩余背包容量可以获得的最大价值为3,所以最优的时候应该是放入物品1;背包容量为3的时候,若放入1物品,获得价值6,剩余背包容量1可以获得的最大价值为0,所以放入物品1可以获得的最大价值为6,如果不放入物品1,那么剩余背包容量3可以获得的最大价值(在已经填充过的部分查找)为3,所以这时也是放入物品1为最优......当背包容量为8的时候放入物品1获得价值6,剩余背包容量6可以获得最大价值为9,放入物品1的最大价值为6+9=15,如果不放入物品1,剩余背包容量8可以获得的最大价值为9,所以此时也是放入物品1最优。

总结:通过上面的分析过程,可以归结为:先考虑这个物品放入的时候可以获得的最大价值(这个物品的价值+剩余背包(背包总容量-该物品重量)容量可以获得的最大价值),再考虑不放入这个物品的时候可以获得的最大价值(剩余背包容量(此时就是背包总重量)可以获得的最大价值),然后将2者进行比较,那种结果的价值大就将哪种结果的价值保存下来,依次类推。

#include<stdio.h>  

const int c = 10;             //背包的容量  
const int w[] = {2,2,6,5,4};//物品的重量 
const int v[] = {6,3,5,4,6};//物品对应的待加  
const int n = sizeof(w)/sizeof(w[0]) - 1 ; //n为物品的个数   
int x[n];  

void package0_1(int m[][10],const int w[],const int v[],const int n)//n代表物品的个数   
{  
    int i, j;
/*********************************最后一个物品单独放置*********************************/  
    for(j = 1; j <= c; j++)  
	{
       if(j < w[n]) /*背包容量<最后一个物品的重量时*/
		   m[n][j-1] = 0;   
       else /*背包能够放下最后一个物品时*/        
		   m[n][j-1] = v[n];  
	}
         
/*********************************放置前n-1个物品*********************************/  
    for(i = n-1; i >= 0; i--)  
        for(j = 1; j <= c; j++) 
		{
           if(j < w[i])   
               m[i][j-1] = m[i+1][j-1];//如果j < w[i]则,当前位置就不能放置,它等于上一个位置的值 
           else //否则,就比较到底是放置之后的值大,还是不放置的值大,选择其中较大者
			   m[i][j-1] = m[i+1][j-1] > m[i+1][j-1-w[i]]+v[i] ? m[i+1][j-1] : m[i+1][j-1-w[i]]+v[i];
		}
}  
void answer(int m[][10],const int n)  
{  
    int j = c-1; /*i = 0, j= c-1坐标上存放着背包容量为c时的最大价值*/ 
    int i; 
	
    for(i = 0; i < n; i++)  
        if(m[i][j] == m[i+1][j]) 
			x[i] = 0;  
        else                
		{   
			x[i] = 1;  /*如果当前物品放入了背包*/
			j = j - w[i];  /*重新计算背包剩余容量,以计算在取最优时其他物品的取舍情况*/
        }
	i -= 1;
    x[n] = m[i][j] ? 1 : 0;   
}  
int main()  
{  
 int m[6][10]={0}; 
 int i, j;
   
 package0_1(m,w,v,n);  
 for(i = 0; i <= 4; i++)  
 {  
     for(j = 0; j < 10; j++)  
     printf("%3d ",m[i][j]);  
     printf("\n");
 }   
 answer(m,n);  
 printf("The best answer is:\n");  
 for(i = 0; i < 5; i++)  
	printf("%d ",  x[i]); 
 printf("\n");

 return 0;  
}  


程序运行结果如下: