动态规划-背包问题总结

01背包问题：

                       01背包其实是一个递推问题，每次都是最优解不断推出最终结果。一维和二维都要掌握。

动态方程：    

                   F[ i , v ] = max { F[ i−1 , v ] , F[ i−1 , v−Ci ]  +  Wi } ，意思是：当选第 i 个物品时 F [ i-1 , v ] 代表不放第 i 件物品，F [ i-1 , v - Ci ] + Wi  ; 代表放第 i 件物品，第 i-1 件物品得到的最优解加上第 i 件物品的价值。可以用一维数组  F[ i ] = max (F[ i ] ,F[ i - ci ]+wi ) ;

代码（二维数组）：

      memset(dp,0,sizeof(dp)) ;
      for(int i=1 ;i<=n ;i++) // 最终答案为f[n][c]
      {
      scanf("%d%d",&v,&w) ; // 边输入边计算
      for(int j=0 ;j<=c ;j++) // 这一行中 j 不能初始化为 v 因为如果这样 i 时就记录（得）不到
       { // i-1 时已经得到的最优解
       dp[i][j]=(i==1 ? 0 : dp[i-1][j]) ;
      if(j>=v&&dp[i][j]<dp[i-1][j-v]+w)
       dp[i][j]=dp[i-1][j-v]+w ;
       }
      }
  
 

代码（一维滚动数组）：

      memset(dp,0,sizeof(dp)) ;
      for(int i=1 ;i<=n ;i++)
      {
      scanf("%d%d",&v,&w) ;
      for(int j=C ;j>=v ;j--) // 这一行可以让 j 大于等于 v 因为结束后f[]数组 
      if(dp[j]<dp[j-v]+w) // 已经把i-1时的最优解保存在里面（因为是一维） 
       dp[j]=dp[j-v]+w ;
      }
  
 

题目类型：

               1. 裸题. 2. 有的只给一个价值，只要把价值同时看成体积就可以了. 3. 有的是求一些物品平分问题（可以用搜索）.4. 让求恰好装满（理解：初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了）.5.让打印路径。

完全背包：

                完全背包只学习了一种方法，二进制方法和多重背包一样。

动态方程：  

               (1) 转化为01背包 f [ i ][ v ] = max { f[ i - 1 ][ v - k*c[ i ] ] + k*w[i] ] { 0<=k*c[i]<=v }

               (2) F[ i ] = max ( F[ i ],F[ i - ci ] + wi ) ; 和 01 背包中的一维数组的一样只是枚举的顺序不同，这里讲一下枚举的循序（背包九讲）：首先想想为什么 01 背包中要按照 v 递减的次序来循环。 让 v 递减是为了保证第 i 次循环中的状态 F[i,v] 是由状态 F[i−1,v −Ci] 递推而来。 换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策 略时，依据的是一个绝无已经选入第 i 件物品的子结果 F[i−1,v −Ci]。而现在完全背 包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时， 却正需要一个可能已选入第 i 种物品的子结果 F[i,v−Ci]，所以就可以并且必须采用 v 递增的顺序循环。这就是这个简单的程序为何成立的道理。

多重背包：

              多重背包只学了二进制优化二维）：

         在这之前，我空间好像转过一个背包九讲，现在我就只对
        01背包和多重背包有点印象了
         先说下 01 背包，有n 种不同的物品，每个物品有两个属性
         size 体积，value 价值，现在给一个容量为 w 的背包，问
         最多可带走多少价值的物品。
        int f[w+1];   //f[x] 表示背包容量为x 时的最大价值 
        for (int i=0; i<n; i++)
      for (int j=w; j>=size[i]; j++)
       f[j] = max(f[j], f[j-size[i]]+value[i]);
         如果物品不计件数，就是每个物品不只一件的话，稍微改下即可
        for (int i=0; i<n; i++)
      for (int j=size[i]; j<=w; j++)
       f[j] = max(f[j], f[j-size[i]]+value[i]);
         f[w] 即为所求
         初始化分两种情况
        1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;
        2、如果不需要正好装满 f[0~v] = 0;
         多重背包问题要求很简单，就是每件物品给出确定的件数，求
         可得到的最大价值
         多重背包转换成 01 背包问题就是多了个初始化，把它的件数C 用
         分解成若干个件数的集合，这里面数字可以组合成任意小于等于C
         的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可
         以用数字的二进制形式来解释
         比如：7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以
         组合成任意小于等于7 的数，而且每种组合都会得到不同的数
        15 = 1111 可分解成 0001  0010  0100  1000 四个数字
         如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成
        7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13
         的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种
         思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。
         看代码：
        int n;  //输入有多少种物品 
        int c;  //每种物品有多少件 
        int v;  //每种物品的价值 
        int s;  //每种物品的尺寸 
        int count = 0; //分解后可得到多少种物品 
        int value[MAX]; //用来保存分解后的物品价值 
        int size[MAX];  //用来保存分解后物品体积 
        scanf("%d", &n); //先输入有多少种物品，接下来对每种物品进行分解 
        while (n--)
         {   //接下来输入n中这个物品 
      scanf("%d%d%d", &c, &s, &v);  //输入每种物品的数目和价值 
      for (int k=1; k<=c; k<<=1) { //<<右移 相当于乘二 
       value[count] = k*v;
       size[count++] = k*s;
       c -= k;
       }
      if (c > 0) {
       value[count] = c*v;
       size[count++] = c*s;
       }
       }
       现在用count 代替 n 就和01 背包问题完全一样了
  
 

分组背包(背包九讲)：

      有n件物品和一个容量为V的背包，第 i 件物品的费用是 Ci ,价值是 Wi , 这些物品被划分为 k 组，每组中的物品相互冲突，最多选一件，求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

算法：

这个问题变成了每组物品有若干中策略：是选择本组的某一件，还是一件都不选。也就是说设F[ k,v ] 表示前 k 组物品花费费用 v 能取得的最大权值，则有：

                    F[ k , v ] = max { F[ k-1 , v ] ,F[k-1,v-Ci ] +Wi } ;

同样可以优化为一维。假设有 k 组物品每组有 m 个物品：

      for(int i=0 ;i<k ;i++) // 组数
       for(int j=V ;j>=0 ;j--) // V 为总体积
      for(int k=0 ;k<m&&v[i][k]<=j ;k++) // 依次放入同组的每个物品
       dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]) ;
  
 

开始一直不明白这样为什么能做到每组物品只选择一件，自己模拟了一下才恍然大悟，因为放同一组的时候体积是逆序放的，而且放同一体积时同一组的都放一次，这样就保证了每组物品最多选一件（可以不选择）。

变形：每组至少选择一件（例题：HDU 3033 ）。

   如果这样初始化时就要注意了，只有第 0 组所有的情况是正确的（组数从 1 开始），so ~ > 其它赋值为负无穷。因为每组物品可以选择多件，因此要把第二层 for 循环与第三层for 循环互换一下。这样就可以保证每组物品可以选择多件。

代码~~>

推荐博客：01背包总结 建议先看背包九讲         

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/18078085