转载

0-1背包问题,用滚动数组,动态规划解决

接触了很多的0-1背包的问题,这个问题是动态规划的经典题,总结一下,加深自己的印象,也

为大家做个参考,对blog有问题可以直接评论,我会尽快的回答!


题目:有N件物品和一个容量为V的背包,第i件物品的体积w[i],价值是c[i],求解将那些物品装入背包

可使这些物品的费用总和不超过背包容量,且使背包内的物品价值总和最大!


F[i][w]----对于前i物品而言,使体积为w的背包内物品价值总和最大,最大的价值为F[i][w].

下面这个方程为整个背包问题的核心:

F[i][w]=max{ F[i-1][w]  ,  F[i-1][w-w[i]]+c[i]  } 

对于第i件物品,你可以选择把它装入背包,还可以选择前i-1件物品对于体积为w的背包的最优解,

选择其中的最大值,就是F[i][w]的值了!

话不多说,直接上代码,更加清楚得了解!


代码1

#include<iostream> 
using namespace std;

int F[100][100]; //定义一个二维数组
int w[100]; //体积数组
int c[100];  //价值数组
int n;   //物品总数
int V;  //背包的体积 

int max(int a,int b);

int main() 
 {
 	
 	while(cin>>n&&cin>>V)
 	{
 	 int i,j; 
 	 
 	 for(i=1;i<=n;i++)//初始化数据 
 	   cin>>w[i]>>c[i];  
     
	 for(i=1;i<=n;i++)		
	  for(j=1;j<=V;j++)
	   if(j>w[i]) 
	  F[i][j]=max(F[i-1][j],F[i-1][j-w[i]]+c[i]);
	  else F[i][j]=F[i-1][j];
 	  cout<<F[n][V];
 	}
 }
int max(int x,int y)
 {
 	
 	return x>y?x:y;
 }
这个代码是,对于二维数组而言,一旦物品数和重量多了起来,程序的复杂度就很大,所以

必须减少时间复杂度,可以从优化空间的角度来看这个问题!


可以用一个滚动数组来代替二维数组,让数组动起来

如果你认真看了代码1,代码2就比较简单的理解!


代码2:

#include<iostream> 
using namespace std;

int F[100]; //定义一个一维数组
int w[100]; //体积数组
int c[100];  //价值数组
int n;   //物品总数
int V;  //背包的体积 

int max(int a,int b);

int main() 
 {
 	
 	while(cin>>n&&cin>>V)
 	{
 	 int i,j; 
 	 
 	 for(i=1;i<=n;i++)//初始化数据 
 	   cin>>w[i]>>c[i];  
     
	 for(i=1;i<=n;i++)		
	  for(j=V;j>=w[i];j--)//从V开始,这是个技巧,我在这就走了很多弯路,有兴趣的同学可以思考                                 一下 
	    
	  F[j]=max(F[j],F[j-w[i]]+c[i]);
	  
 	  cout<<F[V];
 	}
 }
int max(int x,int y)
 {
 	
 	return x>y?x:y;
 }

另外我想说的是,大家可以换个角度思考问题,可以从物品的价值着手!而不是从物品的重量,在某些

特定的条件下,这个是很好用的!

F[i][c]------对于前i物品而言,使背包装上c价值的物品,所需的最小体积!

核心方程:

 F[i][c] = min { F[i-1][c] , F[i-1][c-c[i]] + w[i]  }

对于第i件物品,你可以选择把它装入背包,还可以选择前i-1件物品对于装入价值为c的

背包的最小体积的最优解,

装入体积为V的F[i][c]中最大的C就是最优解,即对于装入V体积的东西,可以获得的最大价值!

问题得到了解决!

代码3:

#include<iostream> 
using namespace std;

int w[100];//体积
int v[100];//价值
int F[100];//一维数组
int Getdata(long int n);//输入数据
int newdata();//初始化数组
int min(int a,int b);
int main()
 {
    int n;
    int W;
   while(cin>>n&&cin>>W)
   {
  	 Getdata(n);
  	 newdata();
  	 int i,j;
  	 int max=0;
  	 int vm=0;//暂存价值的大小
  	 for(i=1;i<=n;i++)//为了时间复杂度的考虑我用了滚动数组
  	 {
  	   vm=vm+v[i];
  	   for(j=vm;j>=1;j--)   
		 if(j>v[i])	
  	   	 F[j]=min(F[j],F[j-v[i]]+w[i]);	 
  	   	 else F[j]=min(F[j],w[i]);   	 
         }
    for(i=1;i<=vm;i++)//找出体积为V的C最大的那个元素
    {
       if((F[i]<=W)&&(i>max)) 
         max=i;       
    }
   cout<<max<<endl;
    }
  return 1;
  } 
int Getdata( int n)
 {
   int i;
   for(i=1;i<=n;i++)
    cin>>w[i]>>v[i];
    return 1;
 }
int newdata()//把数组初始化为最大值
{
  int i;
  for(i=0;i<100;i++)	
   F[i]=10000;
   return 1;
}
int min(int a,int b)
{
  if(a>b) return b;
  else return a;
}

大家有兴趣的话可以做一下这道题:0-1背包实战题

如果大家有问题,可以私聊我,我一定会回答的!共同学习,进步,哈哈!

正文到此结束
本文目录