新编背包九讲（一) - 基础题

• 新编背包九讲（一）- 基础题
  • 01背包问题（只能选一个）
    • DFS解法思路
    • 二维动态规划思路
    • 一维动态规划思路
    • 初始化的细节问题
  • 完全背包问题（无限选取）
    • 基于01思想的二维动态规划
    • 改进迭代公式后的二维动态规划
    • 一维动态规划
  • 多重背包问题（可选数量有限）
    • 基于01思想的二维动态规划

新编背包九讲（一）- 基础题

01背包问题（只能选一个）

1. 参考资料：

   题目： https://www.acwing.com/problem/content/description/2/

   参考视频： https://www.bilibili.com/video/av36136952?from=search&seid=7912323779612203145

2. AC代码：

   //DFS算法复杂度过高
   import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);while (reader.hasNextLine()){int N = reader.nextInt();//N种商品int V = reader.nextInt();//背包容量int[] v = new int[N + 1] ;//商品体积int[] w = new int[N + 1] ;//商品价值for (int i=1 ; i <= N ; i++){v[i] = reader.nextInt();w[i] = reader.nextInt();}//处理背包问题，DFS解法System.out.println(helper(N,V,v,w));//处理背包问题，二维解法// int[][] f = new int[N+1][V+1];// for(int i=1;i<=N;i++){//     for(int j=1;j<=V;j++){//         f[i][j] = f[i-1][j];//         if(j>=v[i])//             f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);//     }// }// System.out.println(f[N][V]);//处理背包问题，一维解法// int[] f = new int[V+1];// for(int i=1;i<=N;i++){//     for(int j=V;j>=v[i];j--){//         f[j] = Math.max(f[j],f[j-v[i]]+w[i]);//     }// }// System.out.println(f[V]);}}static int helper(int N,int V,int[] v,int[] w){if(N==0 || V==0)return 0;int left = helper(N-1,V,v,w);int right = 0;if(V>=v[N])right = helper(N-1,V-v[N],v,w) + w[N];return Math.max(left,right);}
   }
   

DFS解法思路

• 
• B(N,V)表示考虑前N件物品，且背包容量为V的情况下的最大价值。很显然得到如下关系：B(N,V) = max{B(N-1,V),B(N-1,V-v[N])+w[N]}。解释一下，B(N-1,V)表示不购买第N件商品，则考虑前N件和考虑前N-1件没有区别，B(N-1,V-v[N])+w[N]表示购买第N件，此时背包可携带的容量-v[N],携带的价值+w[N]。边界条件是，当背包没有空间（V==0）或者没有商品可以考虑（N=0）。

  static int helper(int N,int V,int[] v,int[] w){if(N==0 || V==0)return 0;int left = helper(N-1,V,v,w);int right = 0;if(V>=v[N])right = helper(N-1,V-v[N],v,w) + w[N];return Math.max(left,right);
  }
  

• 本算法类似二叉树的后序遍历，先计算左右子树再返回max得到根节点数值，最后得到整个搜索树的根节点值。但是本算法时间复杂度为2^N，因此需要优化。怎么优化呢？我们目前DFS搜索时，有很多中间节点是重复计算的，但是其实可以保存下来，即记忆化搜索，即动态规划。

二维动态规划思路

• 
• B(N,V)表示考虑前N件物品，且背包容量为V的情况下的最大价值。很显然得到如下关系：B(N,V) = max{B(N-1,V),B(N-1,V-v[N])+w[N]}。这个基本关系式还是没有变的，但是我们不用递归，而用递推。B(i,j) = max{B(i-1,j),B(i-1,j-v[i])+w[i]},i=[0_N],j=[0V]。两层循环，第一层为只考虑前i件物品，第二层为背包最大容量为j，从[1][1]迭代到[N][V]，相当于我们保存了路径上的每一点的最优值，然后最后的[N][V]就是题目要求的最优值。
• 二维还是比较好理解的，因为是一张表，这张表的特点是每一格都保存了那个格子相应条件（i,j）下的最优值，并且（i,j）的最优值只和之前的状态有关。

  int[][] f = new int[N+1][V+1];
  for(int i=1;i<=N;i++){for(int j=1;j<=V;j++){f[i][j] = f[i-1][j];if(j>=v[i])f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);}
  }
  System.out.println(f[N][V]);
  

• 此时时间复杂度为NV，空间复杂度为NV。但是实际上还可以优化空间复杂度到V。

一维动态规划思路

• 我们希望把代码改成一维数组：

  int[] f = new int[V+1];
  for(int i=1;i<=N;i++){for(int j=1;j<=V;j++){f[i][j] = f[i-1][j];if(j>=v[i])f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);}
  }
  System.out.println(f[V]);
  

• 上面是一个半成品代码，因为如果我们把i的那一维去掉之后，会导致f[i][j] = f[i-1][j];产生毛病，因为我们没有保存f[i][j]和f[i-1][j]，我们只保存了f[j]。有没有一种方式，让我们在对类似f[j]=f[j-v[i]]时，产生和f[i][j]=f[i-1][j-v[i]]一样的效果呢？
• 还真的有。如果我们这样写：内循环从V到1，而不是从1到V。

  int[] f = new int[V+1];
  for(int i=1;i<=N;i++){for(int j=V;j>=1;j--){if(j>=v[i])f[j] = Math.max(f[j],f[j-v[i]]+w[i]);}
  }
  System.out.println(f[V]);
  

  此时，比如当前i循环时执行到f[5] = f[5-v[i]]，因为5-v[i]必然小于5，所以f[5-v[i]]必然还没有被当前i循环处理到，那此时的f[5-v[i]]的值是什么时候写入的呢？必然是上一次i循环时写入的，因此实现了f[j]=f[j-v[i]]时，产生和f[i][j]=f[i-1][j-v[i]]一样的效果。
• 
  从图上来看的话，第一次循环i=1的时候，从后向前走，f[20]]到f[0]我都标记为红色，这也是f[]数组中在这一轮循环中保存的值。而i=2的时候，即绿色时，只要f[20]被替换掉，因此f[20] = f[20 -v[i]] + w[i]的计算相当于用的是上一轮i=1的结果。
• 初学者比如我，老是会有疑惑，但是要记住的是：无论是一维数组还是二维数组，只是保存数据的介质不同，其根本还是那张搜索的二维表。不是说二维数组的时候就是二维表，一维数组的时候就是一维表，本质都是二维表，只是一维数组只保存解题需要的必要信息而已。

初始化的细节问题

• 对于上述问题有两种表述1.背包被恰好装满时的最大价值。2.背包能携带的最大价值。对于情况1，从物理角度来说，题目要求恰好装满，说明F[0][1]不可能作为初始解，因为F[0][1]的物理意义为：背包空间为1时考虑0件物品，当某一状态F[1][v]是从F[0][1]转换而来，物理意义就是在背包容量为1且不携带物品的基础上可以转移到F[1][v]这个最优解，但是基础的这个状态是不符合题意的。F[1][v]必须只能从F[0][0]转移过来。
• 程序怎么写呢？在二维情况下，F[0][0]=0，F[0][1_{V]=-无穷，在一维情况下F[0]=0,F[1}V]=-无穷。

完全背包问题（无限选取）

1. 参考资料

   题目： https://www.acwing.com/problem/content/3/

2. AC代码

   import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);while (reader.hasNextLine()) {int N = reader.nextInt();//N种商品int V = reader.nextInt();//背包容量int[] v = new int[N + 1];//商品体积int[] w = new int[N + 1];//商品价值for (int i = 1; i <= N; i++) {v[i] = reader.nextInt();w[i] = reader.nextInt();}//01背包问题转换而来的思路// int[][] f = new int[N+1][V+1];// for(int i=1;i<=N;i++){//      for(int j=1;j<=V;j++){//          f[i][j] = f[i-1][j];//          int k = 1;//          while(j-k*v[i]>=0){//              f[i][j] = Math.max(f[i][j],f[i-1][j-k * v[i]]+ k * w[i]);//              k++;//          }//      }//  }//  System.out.println(f[N][V]);//进一步的二维数组解决思路// int[][] f = new int[N+1][V+1];// for(int i=1;i<=N;i++){//     for(int j=1;j<=V;j++){//         f[i][j] = f[i-1][j];//         if(j>=v[i])//             f[i][j] = Math.max(f[i-1][j],f[i][j-v[i]]+w[i]);//     }// }// System.out.println(f[N][V]);//一维解决思路int[] f = new int[V+1];for(int i=1;i<=N;i++){for(int j=v[i];j<=V;j++){f[j] = Math.max(f[j],f[j-v[i]]+w[i]);}}System.out.println(f[V]);}}
   }
   

基于01思想的二维动态规划

• 因为可以无限次选择，因此增加参数k，k的范围在1到j/v[i]，因此要用三层循环，虽然还是NV个状态，但是因为多了一层循环，总体复杂度要超过01背包问题。

  int[][] f = new int[N+1][V+1];
  for(int i=1;i<=N;i++){for(int j=1;j<=V;j++){f[i][j] = f[i-1][j];int k = 1;while(j-k*v[i]>=0){f[i][j] = Math.max(f[i][j],f[i-1][j-k * v[i]]+ k * w[i]);k++;}}}System.out.println(f[N][V]);
  

改进迭代公式后的二维动态规划

• 反思一下我们的迭代公式f[i][j] = Math.max(f[i][j],f[i-1][j-k * v[i]]+ k * w[i]);,这是在01背包问题的基础上增加了k这个系数。我们再转过头去看看01背包问题的地推公式，B(i,j) = max{B(i-1,j),B(i-1,j-v[i])+w[i]},i=[0_N],j=[0V]。你是否有过疑问，为什么是B(i-1,j-v[i])+w[i]而不是B(i,j-v[i])+w[i]？相信你也说服了自己，因为如果选取了第i件物品，那么必须从只考虑前i-1件商品的子状态中选取… 等等，在完全背包中，如果选取了第i件物品，背包的限制为j0，那么还是从i-1去搜么？不是了，我们应该从i去搜，因为第i件物品可以取无数次！
• 所以写出新的迭代公式：f[i][j] = Math.max(f[i-1][j],f[i][j-v[i]]+w[i]);。即，f[i][j-v[i]]+w[i]，如果我选择了当前物品，那我看看在本轮i循环中我是否还选取过这个物品（j-v[i]>=0），如果选择过,那么我无妨再选择一次。

  int[][] f = new int[N+1][V+1];
  for(int i=1;i<=N;i++){for(int j=1;j<=V;j++){f[i][j] = f[i-1][j];if(j>=v[i])f[i][j] = Math.max(f[i-1][j],f[i][j-v[i]]+w[i]);}
  }
  System.out.println(f[N][V]);
  

一维动态规划

• 根据状态转移公式：f[i][j] = Math.max(f[i-1][j],f[i][j-v[i]]+w[i])，当我们走到第i次循环的第j个点时，f[j]在赋值之前就是f[i-1][j]，且因为j-v[i]< j，因此f[j-v[i]]必然在f[j]之前被计算，所以f[j-v[i]]等价于f[i][j-v[i]]，这样就清楚了，我们其实可以直接把二维动态规划换成一维就行了，不用向01背包问题一样倒序。

  int[] f = new int[V+1];
  for(int i=1;i<=N;i++){for(int j=v[i];j<=V;j++){f[j] = Math.max(f[j],f[j-v[i]]+w[i]);}
  }
  System.out.println(f[V]);
  

• 倒序的物理意义代表只能选择一次，顺序的物理意义代表可以选择多次。

多重背包问题（可选数量有限）

1. 参考资料

   题目： https://www.acwing.com/problem/content/4/

2. AC代码

   import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);while (reader.hasNextLine()) {int N = reader.nextInt();//N种商品int V = reader.nextInt();//背包容量int[] v = new int[N + 1];//商品体积int[] w = new int[N + 1];//商品价值int[] n = new int[N + 1];//商品最大选取数量for (int i = 1; i <= N; i++) {v[i] = reader.nextInt();w[i] = reader.nextInt();n[i] = reader.nextInt();}//01背包问题转换而来的思路int[][] f = new int[N+1][V+1];for(int i=1;i<=N;i++){for(int j=1;j<=V;j++){f[i][j] = f[i-1][j];int k = 1;while(k<=n[i] && j-k * v[i]>=0){f[i][j] = Math.max(f[i][j],f[i-1][j-k * v[i]]+ k * w[i]);k++;}}}System.out.println(f[N][V]);}}
   }
   

基于01思想的二维动态规划

• 这个就很简单了，完全背包问题的k的范围在1到j/v[i]，多重背包问题的k的范围在1到j/v[i]且在1到n[i]之间。

  int[][] f = new int[N+1][V+1];
  for(int i=1;i<=N;i++){for(int j=1;j<=V;j++){f[i][j] = f[i-1][j];int k = 1;while(k<=n[i] && j-k * v[i]>=0){f[i][j] = Math.max(f[i][j],f[i-1][j-k * v[i]]+ k * w[i]);k++;}}
  }
  System.out.println(f[N][V]);
  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！