0/1背包问题-递归、动态规划

问题描述：给定n种物品和一个背包，物品I的重量是Wi，其价值为Vi，背包的容量为c，问如何选择装入

背包的物品，使得装入背包的物品的总价值最大？

形式化描述：给定c求一个n元1-0向量Xi（每种物品要么装要么不装）
            Wi Xi（i从1到n连乘累加，Xi=0或1）〈=c
            Vi Xi（i从1到n连乘累加，Xi=0或1） 达到最大

/*f(j,x)是当背包载重为x，可供选择的物品为0，1...j时的最优解*/
/*最优解的递归式：*/
/* f(-1,x)=-9999（负无穷大） x<0 */
/* f(-1,x)=0 x>=0 */
/* f(j,x)=max{ f(j-1,x), f(j-1,x-w[j])+p[j] } 0<=j<n */

//背包问题的递归解法
#include<iostream>
using namespace std;

int n=3;
float w[3]={2,3,4};
int p[3]={1,2,4};
float M=6.0;

int nap(int j,float X) //返回收益
{
if(j<0) return( (X<0) ? -9999:0);
if(X<w[j]) return nap(j-1,X);
else
{
   int a=nap(j-1,X);
   int b=nap(j-1,X-w[j])+p[j];
   return a>b? a:b;
}
}

int main()
{
cout<<nap(n-1,M)<<endl;
system("pause");
return 0;
}

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

高级程序员教程里有，不过，是递归算法实现背包问题；

try(物品i，当前选择已达到的重量和tw,本方案可能到达的总价值tv)
{ /* 考虑物品i包含在当前方案中的可能性 */
   if(包含物品i是可接受的）
      {
         将物品i包含在当前方案中；
         if(i<n-1)
           {
             try(i+1,tw+物品i的重量，tv);
            }
         else
           {
             /*又一个完整方案，因此比前面的方案好，以它作为最佳方案*/
             当前方案作为最佳方案保存；
            }
         恢复物品i不包含状态；
      }
   /*考虑物品i不包含在此方案中的可能性*/
   if(不包含物品i仅是可能的）
     {
          if(i<n-1)
             {
                try(i+1,tw,tv-物品i的价值)
              }
          else
             {
              /*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/  
              以当前方案作为最佳方案保存；
             }
      }
}

#include<iostream>
using namespace std;
#define N 100

double limitw,tolv,maxv;
int option[N],cop[N];
struct
{
double w;
double v;
}a[N];

int n;   //物品数量

void find(int i,double tw,double tv)
{
int k;
if(tw+a[i].w<=limitw)             // 包含物品i是可接受的
{
cop[i]=1;
if(i<n-1) find(i+1,tw+a[i].w,tv);
else
{
    for(k=0;k<n;++k)
      option[k]=cop[k];
    maxv=tv;
}
cop[i]=0;
}
if(tv-a[i].v>maxv)              // 不包含物品i仅是可考虑的
if(i<n-1) find(i+1,tw,tv-a[i].v);
else
{
   for(k=0;k<n;++k)
     option[k]=cop[k];
   maxv=tv-a[i].v;
}
}
   
    
int main()
{
int k;
double w,v;
tolv=0.0;
cout<<"Input the total number:\n";
cin>>n;
cout<<"Input the weight and value of everyone\n";
for(k=0;k<n;++k)
{
   cin>>w>>v;
   a[k].w=w; a[k].v=v;
   tolv+=a[k].v;
}
cout<<"Input the limit weight\n";
cin>>limitw;
maxv=0.0;
for(k=0;k<n;++k) cop[k]=0;
find(0,0.0,tolv);
cout<<"The choices number is \n";
for(k=0;k<n;++k)
    if(option[k]) cout<<k+1<<" ";    //从1开始计数
   
cout<<"\nThe total value: \n"<<maxv<<endl;

system("pause");
return 0;
}

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

for(int i=1;i<n;i++)
{
   for(int j=0;j<=c;j++)
   {
      if(j+W[i]<=c && f[i-1][j]+V[i]>f[i][j+W[i]])
         f[i][j+W[i]]=f[i-1][j]+V[i];
   }
}

最大值是 max{ f[n-1][k] }(0<=k<=c)

设f(n,w)表示前n个物品装w公斤重时的最大价值
递推式为
f(i,w)=max{f(i-1,w),f(i-1,w-wi)+vi}
算法如下：
开始时候f(0,i)=0 0<=i<=c
for i=1 to n
f(i,0)=0
for j=1 to c
    f(i,j)=f(i-1,j)
    if w(i)<=j and f(i,j)<f(i-1,j-w(i))+v(i) then
       f(i,j)=f(i-1,j-w(i))+v(i)
end j
end i

---------------------------------------------------------------
#include<stdio.h>
int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n)
{
int i,j,w[10],p[10];
for(i=1;i<n+1;i++)
        scanf("\n%d,%d",&w[i],&p[i]);
for(i=0;i<10;i++)
      for(j=0;j<100;j++)
           c[i][j]=0;/*初始化数组*/
for(i=1;i<n+1;i++)
      for(j=1;j<m+1;j++)
           {
            if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
                     {
                      if(c[i-1][j]<p[i]+c[i-1][j-w[i]])
                           /*如果本物品的价值加上背包剩下的空间能放的物品的价值大于上一次选

择的最佳方案则更新c[i][j]*/
                            c[i][j]=p[i]+c[i-1][j-w[i]];
                      else
                            c[i][j]=c[i-1][j];
                     }
              else c[i][j]=c[i-1][j];
            }
return(c[n][m]);
                    
}
int main()
{
    int m,n;int i,j;
    scanf("%d,%d",&m,&n);
    printf("Input each one:\n");
    printf("%d",knapsack(m,n));
    printf("\n");/*下面是测试这个数组,可删除*/
     for(i=0;i<10;i++)
      for(j=0;j<15;j++)
         {
          printf("%d ",c[i][j]);
             if(j==14)printf("\n");
         }
    system("pause");
}

/**  
* @author zyf 题目：给定n个物体，其中第i个物体重量wi，价值vi ，另有一个最大载重W的背包，往

里面塞东西使得总价值尽可能大  
*   
* 令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值   
* f(i,j)=max{f(i-1,j), f(i-1, j-w[i])+v[i] } ,i>0, j>=w[i];   
* f(i,j) = f(i-1,j) , i>0, j<w[i];   
* f(0,j) = v[0] , i=0, j>=w[0];   
* f(0,j) = 0, i=0, j<w[0];  
*   
*/  
public class bagPro {   
  
    /**  
     * @param args  
     */  
    public static void main(String[] args) {   
        // TODO 自动生成方法存根   
           
           
        int w[] = {2,2,6,5,4};   
        int v[] = {6,3,5,4,6};   
        int c = 10;   
        int f[][] = new int [5][c+1];          
           
        int maxValue = 0;   
           
        for(int j=0 ; j<=c; j++){   
            if(j>=w[0])   
                f[0][j] =v[0];   
            else    
                f[0][j] = 0;   
        }   
           
        for(int i=1; i<w.length; i++){   
            for(int j=0; j<=c;j++){   
                if(j<w[i])   
                    f[i][j] = f[i-1][j];   
                else if(f[i-1][j]>=f[i-1][j-w[i]]+v[i])   
                    f[i][j] = f[i-1][j];   
                else  
                    f[i][j] = f[i-1][j-w[i]]+v[i];   
            }   
        }   
           
        System.out.println(f[4][c]);   
           
    }   
}   

评论

2 楼 leizisdu 2011-11-15  

引用

if(不包含物品i仅是可能的）

感觉有些拗口

1 楼 leizisdu 2011-11-14  

博主，你牛！谢谢您的讲解