您的位置: 首页  >  文章  >  0--1背包问题（动态规划）

0--1背包问题（动态规划）

分类: 文章 • 2024-11-21 17:07:21

1、问题描述：

     给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

例子：数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6}

下面是算法分析的过程：

      其实这里就是选择装与不装的问题关键

　　（1）对于m[5][j]，当j<w[5]时，物品5不能放入背包中，此时背包的价值为0。当j>=w[5]时，物品5可以放入背包，此时背包的价值为v[5]。得到结果如下表：       
         W            i        0         1        2          3          4         5           6           7         8          9           10         V

2 1                       6
2 2                       3
6 3                       5
5 4
                  4
4 5 0
 0
 0 0
 6 6 6 6 6 6 6 6
      （2）在物品5的基础上分析物品4，

　　当j<w[4]时，物品4不能放入，此时背包的最大价值为m[4+1][j]；即m[4][0..4]=m[5][0..4]

　　当j>=w[4]时，物品4要么放入要么不放入。当物品4放入背包后，对于物品4+1到n，能达到的最大价值为m[4+1][j-w[4]]+v[4]，故此时能达到的最大价值为m[4+1][j-w[4]]+v[4]

　　当物品4不放入背包时，能达到的最大价值为m[4+1][j]。最后比较放入与不放入情况下，两者的最大值取其大者，分析结果如上表的橙色：

0--1背包问题（动态规划）

当W【4】>j时，则物品4不能放入，所以m（4，j）=m（5，j）且m（4，0--4）=m（5，0--4）

         W            i        0         1        2          3          4         5           6           7         8          9           10         V

2 1 0 1 2 3 4 5 6 7 8 9 10 6
2 2                       3
6 3                       5
5 4 0
 0 0 0 6             4
4 5 0
 0
 0 0
 6 6 6 6 6 6 6 6
当j>=4时，对物品4要么放入要么不放入，最优值得选择标准应依据总价值，总价值高的作为最优值，例如m（4，5），如果w4不放入的时候，原值，总价值为m（4+1，5）=6；

当w4放入的时候，则配合其前边的最优值，即w4放入，使剩下物品最大容量为j-w4，则背包最大容量为m（4+1，j-w4）的值为0再加上v4，然后再与前面不放入的m（4+1，5）作比较，发现m（4+1，j-w4）=4<m（4+1，5）=6,所以选择不放入，依次类推即可

         W           i        0         1        2          3          4         5           6           7         8          9           10          V

2 1                       6
2 2                       3
6 3                       5
5 4 0
 0 0 0 6 6 6 6 6 10 10 4
4 5 0
 0
 0 0
 6 6 6 6 6 6 6 6
最后得出结果为：

                                   
       W            i        0         1        2          3          4         5           6           7         8          9           10           V

2 1 0 0 6 6 9 9 12 12 15 15 15 6
2 2 0 0 3 3 6 6 9 9 9 10 11 3
6 3 0
 0 0 0 6 6 6 6 6 10 11 5
5 4 0
 0 0 0 6 6 6 6 6 10 10 4
4 5 0
 0
 0 0
 6 6 6 6 6 6 6 6

  1. #include<iostream>  
  2. #include<algorithm>  
  3. using namespace std;  
  4. void Knapsack(int *v,int *w,int n,int c,int **m)  
  5. {  
  6.     int jMax=min(w[n]-1,c);///背包剩余量的上限(0~~w[n]-1)  
  7.     for(int i=0;i<=jMax;i++)  
  8.     {  
  9.         m[n][i]=0;  
  10.     }  
  11.     for(int j=w[n];j<=c;j++)///例如这里是当j>w[5]的时候，则装入该物品的价值  
  12.     {  
  13.         m[n][j]=v[n];  
  14.     }  
  15.     ///以上算是对最后一行符合条件的进行赋值  
  16.     for(int i=n-1;i>1;i--)///从下往上开始  
  17.     {  
  18.        jMax=min(w[i]-1,c);  
  19.        for(int j=0;j<=jMax;j++)///当不能装入的时候  
  20.         {  
  21.             m[i][j]=m[i+1][j];  
  22.         }  
  23.        for(int j=w[i];j<=c;j++)///当可以装入的时候  
  24.        {  
  25.             m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);  
  26.        }  
  27.     }  
  28.     m[1][c]=m[2][c];  
  29.     if(c>w[1])  
  30.     {  
  31.         m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);  
  32.     }  
  33. }  
  34.   
  35. void TraceBack(int **m,int *w,int c,int n,int *x)  
  36. {  
  37.      for(int i=1;i<n;i++)  
  38.      {  
  39.          if(m[i][c]==m[i+1][c])///没有装入的时候  
  40.          {  
  41.            x[i]=0;  
  42.          }  
  43.          else///这里是能装进去的时候  
  44.          {  
  45.             x[i]=1;  
  46.             c-=w[i];  
  47.          }  
  48.      }  
  49.      x[n]=(m[n][c])?1:0;  
  50. }  
  51. int main()  
  52. {  
  53.     int c,n;  
  54.     cout<<"输入物品的总个数：";  
  55.     cin>>n;  
  56.     cout<<endl<<"输入能装进物品的总重量:";  
  57.     cin>>c;  
  58.     int *w=new int[n];  
  59.     int *v=new int[n];  
  60.     int *x=new int[n];  
  61.     int **m=new int *[n];  
  62.     for(int i=1;i<=n;i++)  
  63.     {  
  64.         m[i]=new int[c];  
  65.     }  
  66.     cout<<endl<<"输入每个物品分别所对应的重量：";  
  67.     for(int i=0;i<=n;i++)///输入物品的重量（注意，一开始我是以下标为1开始的，所以这里我输入的时候，下标0应该输入的是0）  
  68.     {  
  69.         cin>>w[i];  
  70.     }  
  71.     cout<<endl<<"输入每个物品分别所对应的价值：";  
  72.     for(int i=0;i<=n;i++)///输入物品的价值（注意，一开始我是以下标为1开始的，所以这里我输入的时候，下标0应该输入的是0）  
  73.     {  
  74.         cin>>v[i];  
  75.     }  
  76.     cout<<endl<<endl<<"输出每个物品的重量分别为如下："<<endl;  
  77.     for(int i=1;i<=n;i++)  
  78.     {  
  79.         cout<<i<<"号物品重量为:"<<w[i]<<"Kg  "<<"其价值为:"<<v[i]<<endl<<endl;  
  80.     }  
  81.     Knapsack(v,w, n,c,m);  
  82.     cout<<endl<<"输出背包能装的最大价值为："<<m[1][c]<<endl;  
  83.     TraceBack(m,w, c, n,x);  
  84.     cout<<endl<<"输出能装入背包的先后次序如下："<<endl;  
  85.     for(int i=1;i<=n;i++)  
  86.     {  
  87.         if(x[i]==1)  
  88.             cout<<endl<<i<<"号"<<endl;  
  89.     }  
  90.     return 0;  
  91. }
运行结果如下：

0--1背包问题（动态规划）

相关推荐