动态规划篇——背包问题

本次我们介绍动态规划篇的背包问题   
    
    
    
，我们会从下面几个角度来介绍：

背包问题概述 零一背包问题 完全背包问题 多重背包问题 分组背包问题

背包问题概述

背包问题算是很经典的动态规划问题


     


     


     


，我们在面试中也经常出现

首先我们给出动态规划的思想：

然后我们简单介绍一下背包问题：

/*背包问题*/ 有 N 件物品和一个容量是 V 的背包   
    
    
    
。 第 i 件物品的体积是 vi 




 




 




 ，价值是 wi


     


     


     


。 求解将哪些物品装入背包   

   

   

   
，可使这些物品的总体积不超过背包容量

     

     

     

，且总价值最大
  




  




  




 ，输出最大价值 




 




 




 。 /*输入格式*/ 第一行两个整数  


  


  


  
，N 
     
     
     
，V

   




   




   




 ，用空格隔开 



 



 



 
，分别表示物品数量和背包容积   

   

   

   
。 接下来有 N 行                 ，每行两个整数 vi,wi


    




    




    




 ，用空格隔开















，分别表示第 i 件物品的体积和价值

     

     

     

。 /*输出格式*/ 输出一个整数                  ，表示最大价值
  




  




  




 。

最后我们介绍我们下列将要讲述了背包问题的前提：

/*01背包问题*/ 每件物品只能使用一次 /*完全背包问题*/ 每件物品无次数限制使用 /*多重背包问题*/ 每件物品有不同的使用次数 /*分组背包问题*/ 每组物品有若干个


     



     



     



 ，同一组内的物品最多只能选一个

零一背包问题

我们首先介绍一下01背包规则：

/*背包问题*/ 有 N 件物品和一个容量是 V 的背包  


  


  


  
。 第 i 件物品的体积是 vi














，价值是 wi 
     
     
     
。 求解将哪些物品装入背包   
    
    
    
，可使这些物品的总体积不超过背包容量


     


     


     


，且总价值最大 




 




 




 ，输出最大价值

   




   




   




 。 /*输入格式*/ 第一行两个整数   

   

   

   
，N

     

     

     

，V
  




  




  




 ，用空格隔开  


  


  


  
，分别表示物品数量和背包容积 



 



 



 
。 接下来有 N 行 
     
     
     
，每行两个整数 vi,wi

   




   




   




 ，用空格隔开 



 



 



 
，分别表示第 i 件物品的体积和价值                 。 /*输出格式*/ 输出一个整数                 ，表示最大价值


    




    




    




 。 /*限制条件*/ 每件物品只能使用一次

然后我们对其进行分析：

/*内容分析*/ 首先我们有 N 件物品


    




    




    




 ，总容量为 V 如果我们想要求得最大 W 的情况















，我们就需要计算所有的 N 和 V 情况 /*暴力求解方法分析*/ 我们这里首先采用最暴力的方法（二维）： 我们采用f[i][j]来表示前i件物品中进行选择                  ，其体积不超过j


     



     



     



 ，储存值为W最优解 我们会发现














，f[i][j]无非就两种情况： 在i比前一位增加一位后   
    
    
    
，如果我们当前的i没有包含最后一位


     


     


     


，那么一切都和上一位i的结果相同（f[i][j] = f[i-1][j]） 那么我们就只需要判断是否需要加上第i位 




 




 




 ，且前提是j >= v[i]（f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i])） /*优化方法分析*/ 下面我们介绍的优化方法来自于滚动数组： 滚动数组是指当我们只需要两行数据时   

   

   

   
，我们可以抛出二维的概念

     

     

     

，采用层级差来覆盖掉之前的数据信息
  




  




  




 ，从而转换为一维 我们对上述暴力求解进行分析： 我们会发现其实我们所采用的无非只有两行：f[i]和f[i-1] 那么我们只需要将f[i]所使用的f[i-1]的信息在使用前保留下来  


  


  


  
，我们就可以将其简化为一行,也就是一维

我们给出实际代码以及代码中的解析：

/*暴力求解方法*/ import java.util.Scanner; public class Packsack01 { final static int N = 1010; static int n,m; // 存放f[][],v[],w[] static int[][] f = new int[N][N]; static int[] v = new int[N]; static int[] w = new int[N]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); // 首先我们应该初始化f[][] 
     
     
     
，但是由于需要初始化为0

   




   




   




 ，数组默认为0 



 



 



 
，所以我们不需要书写 // 然后我们放入v                 ，w for (int i = 1; i <= n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } // 然后我们就可以逐层更新(第0层为前0个物品


    




    




    




 ，肯定都是0















，不用更新) for (int i = 1; i <= n; i++) { // 我们对前i个物品的体积v也进行递增 for (int j = 0; j <= m; j++) { // 如果我们不加入最后一个数                  ，那么当前i层的值和i-1层的值相同 f[i][j] = f[i-1][j]; // 注意：由于加入第i个数不一定是最优解


     



     



     



 ，所以我们需要进行w权重比较 // 我们比较的数据分别是上一层的不加i的w // 注意这里由于上面f[i][j] = f[i-1][j]














，所以下面的f[i][j]实际上是上一层的f[i-1][j] // 以及我们该层加上i之后的w   
    
    
    
，我们加上i之后v就需要去掉v[i] // 同时我们选取前i-1个数的v为j-[v[i]]的w最优解加上w[i]来进行比较 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][m]); } } /*优化求解方法*/ import java.util.Scanner; public class Packsack01 { final static int N = 1010; static int n,m; // 存放f[],v[],w[] static int[] f = new int[N]; static int[] v = new int[N]; static int[] w = new int[N]; // 建议和暴力求解对比观看 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); // 首先我们应该初始化f[]


     


     


     


，但f[0]最开始都是0 




 




 




 ，就不需要初始化了 // 然后我们放入v   

   

   

   
，w for (int i = 1; i <= n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } // 然后我们就可以逐层更新 for (int i = 1; i <= n; i++) { // 我们对前i个物品的体积v也进行递增 // 注意：由于下面判断条件需要保证j>=v[i]

     

     

     

，所以我们这里可以直接从v[i]开始
  




  




  




 ，毕竟前面的条件都不满足 // 注意：我们这里需要倒叙书写  


  


  


  
， 因为我们下面要使用f[i-1][j-v[i]]这里的i-1就是上一层 
     
     
     
，我们需要注意我们不能覆盖掉这一层！！！ for (int j = m; j >= v[i]; j--) { // 这里简化i之后

   




   




   




 ，为f[j] = f[j] 



 



 



 
，恒等式                 ，我们就直接省略了 // 注意：由于加入第i个数不一定是最优解


    




    




    




 ，所以我们需要进行w权重比较 // 我们比较的数据分别是上一个不加i的w // 以及我们该层加上i之后的w















，我们加上i之后v就需要去掉v[i] // 同时我们选取前i-1个数的v为j-[v[i]]的最优解来进行比较                  ，记得加上w[i] // 这里我们需要注意


     



     



     



 ，我们后面比较的值是上一层的f // 所以我们前面的for循环的方向需要转换一下














，防止上一层的数据被覆盖掉 f[j] = Math.max(f[j],f[j-v[i]]+w[i]); } } // 最后输出即可 System.out.println(f[m]); } }

完全背包问题

我们首先介绍一下完全背包规则：

/*背包问题*/ 有 N 件物品和一个容量是 V 的背包















。 第 i 件物品的体积是 vi   
    
    
    
，价值是 wi                  。 求解将哪些物品装入背包


     


     


     


，可使这些物品的总体积不超过背包容量 




 




 




 ，且总价值最大   

   

   

   
，输出最大价值


     



     



     



 。 /*输入格式*/ 第一行两个整数

     

     

     

，N
  




  




  




 ，V  


  


  


  
，用空格隔开 
     
     
     
，分别表示物品数量和背包容积














。 接下来有 N 行

   




   




   




 ，每行两个整数 vi,wi 



 



 



 
，用空格隔开                 ，分别表示第 i 件物品的体积和价值   
    
    
    
。 /*输出格式*/ 输出一个整数


    




    




    




 ，表示最大价值


     


     


     


。 /*限制条件*/ 每件物品没有使用次数限制

然后我们对其进行分析：

/*内容分析*/ 首先我们有 N 件物品















，总容量为 V 如果我们想要求得最大 W 的情况                  ，我们就需要计算所有的 N 和 V 情况 /*暴力求解方法分析*/ 我们首先介绍暴力求解方法： 我们其实所有步骤和01背包的步骤相似


     



     



     



 ，但不同的是对于第i个物品的数量的大小的决定 我们在不能承载第i个物品前：f[i][j] = f[i-1][j] 在我们能承载第i个物品后：f[i][j] = Math.max(f[i-1][j],f[i-1][j - k*v[i]] + k * w[i]) 所以我们只需要在01背包基础上加上一个fork循环来控制第i个物品的数量保证最优解即可 /*优化方法1分析*/ 我们在上述暴力求解中直接采用了fork循环














，这时我们的时间复杂度在 O(n^3)   
    
    
    
，所以我们想要减少时间复杂度 我们可以发现


     


     


     


，我们上述承载第i个物品后：f[i][j] = Math.max(f[i-1][j],f[i-1][j - k*v[i]] + k * w[i]) 那么相当于：f[i][j] = Math.max(f[i-1][j],f[i-1][j-v[i]]+w[i] 




 




 




 ，f[i-1][j-2*v[i]]+2*w[i],...) 相当于我们直接在上一个f[i][j]的基础上判断是否能够添加i物品   

   

   

   
，也就是：f[i][j] = Math.max(f[i][j],f[i][j-v[i]]+w[i]) /*优化方法2分析*/ 最后一重优化其实就是01背包的优化

     

     

     

，我们转化为滚动数组即可 下面我们介绍的优化方法来自于滚动数组： 滚动数组是指当我们只需要两行数据时
  




  




  




 ，我们可以抛出二维的概念  


  


  


  
，采用层级差来覆盖掉之前的数据信息 
     
     
     
，从而转换为一维 我们对上述暴力求解进行分析： 我们会发现其实我们所采用的无非只有两行：f[i]和f[i-1] 那么我们只需要将f[i]所使用的f[i-1]的信息在使用前保留下来

   




   




   




 ，我们就可以将其简化为一行,也就是一维

我们给出实际代码以及代码中的解析：

/*暴力求解算法*/ import java.util.Scanner; public class PacksackFull { final static int N = 1010; static int n,m; static int[][] f = new int[N][N]; static int[] v = new int[N]; static int[] w = new int[N]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 1; i <= n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // 重点在这里！！！ // 我们之前的f[i][j] = f[i-1][j]也融入到下面的max判断里去了 // 我们由于需要判断第i个物品的数量 



 



 



 
，我们需要从0开始                 ，判断应该增加几个i物品 for (int k = 0; k * v[i] <= j; k++) { f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k); } } } System.out.println(f[n][m]); } } /*优化算法1*/ import java.util.Scanner; public class PacksackFull { final static int N = 1010; static int n,m; static int[][] f = new int[N][N]; static int[] v = new int[N]; static int[] w = new int[N]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 1; i <= n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // 我们为了减少一层循环


    




    




    




 ，我们直接将f[i][j]与前面的f[i][j]比较即可 // 注意：记得先给当前f[i][j]赋值 f[i][j] = f[i-1][j]; // 然后我们才能进行比较















，我们将f[i-1][j]与f[i]层的比较（记得判断是否可以加v[i]！） if(j >= v[i]) f[i][j] = Math.max(f[i][j],f[i][j-v[i]]+w[i]); } } System.out.println(f[n][m]); } } /*优化算法2*/ import java.util.Scanner; public class PacksackFull { final static int N = 1010; static int n,m; static int[] f = new int[N]; static int[] v = new int[N]; static int[] w = new int[N]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 1; i <= n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } for (int i = 1; i <= n; i++) { // 注意：由于这次我们使用的是第i层的数据                  ，所以我们需要从前往后遍历提前更新第i层数据


     



     



     



 ，防止使用第i-1层数据 for (int j = v[i]; j <= m; j++) { if(j >= v[i]) f[j] = Math.max(f[j],f[j-v[i]]+w[i]); } } System.out.println(f[m]); } }

多重背包问题

我们首先介绍一下多重背包规则：

/*背包问题*/ 有 N 件物品和一个容量是 V 的背包 




 




 




 。 第 i 种物品最多有 si 件














，每件体积是 vi   
    
    
    
，价值是 wi   

   

   

   
。 求解将哪些物品装入背包


     


     


     


，可使这些物品的总体积不超过背包容量 




 




 




 ，且总价值最大   

   

   

   
，输出最大价值

     

     

     

。 /*输入格式*/ 第一行两个整数

     

     

     

，N
  




  




  




 ，V  


  


  


  
，用空格隔开 
     
     
     
，分别表示物品数量和背包容积
  




  




  




 。 接下来有 N 行

   




   




   




 ，每行三个整数 vi,wi,si 



 



 



 
，用空格隔开                 ，分别表示第 i 种物品的体积   
    
    
    
、价值和数量  


  


  


  
。 /*输出格式*/ 输出一个整数


    




    




    




 ，表示最大价值 
     
     
     
。 /*限制条件*/ 每个物品有一定的使用次数限制

然后我们对其进行分析：

/*内容分析*/ 首先我们有 N 件物品















，总容量为 V 如果我们想要求得最大 W 的情况                  ，我们就需要计算所有的 N 和 V 情况 /*暴力求解方法分析*/ 其实暴力求解方法和完全背包问题暴力求解方法完全相同 只不过是在k的限制条件上多加了一个k < s[i]的限制而已 /*优化方法分析*/ 我们需要注意多重背包优化由于有数量限制的原因


     



     



     



 ，无法使用完全背包优化！ 我们因为多重背包有数量限制














，当数量较少时   
    
    
    
，我们采用暴力求解是没有问题的


     


     


     


，但是当s数量过多 




 




 




 ，高达一两千就会导致问题 我们的优化思路是 通过将该物品打包分类为多个新的物品   

   

   

   
，重新定义这些物品的v和w

     

     

     

，s固定为1 我们选择2的n次幂来打包物品
  




  




  




 ，因为2的n次幂相加可以组成2的n+1次幂内的所有数！

我们给出实际代码以及代码中的解析：

/*暴力求解算法*/ import java.util.Scanner; public class PacksackNumber { final static int N = 1010; static int n,m; // 多添加一个s数组存放个数 static int[][] f = new int[N][N]; static int[] v = new int[N]; static int[] w = new int[N]; static int[] s = new int[N]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 1; i <= n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); s[i] = scanner.nextInt(); } for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // 重点在这里！！！ // 我们只需要多一个条件 k <= s[i]即可 for (int k = 0; k <= s[i] && k * v[i] <= j; k++) { f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k); } } } System.out.println(f[n][m]); } } /*优化算法*/ import java.util.Scanner; public class PacksackNumber { // 因为是二进制  


  


  


  
，一个数最多就是2的12次方就会超过题目给的2000 
     
     
     
，所以给个将限制范围1000*12 final static int N = 12000; static int n,m; // 这里的f采用一维即可

   




   




   




 ，因为最后我们会转变为01问题 



 



 



 
，可以采用滚动数组优化 static int[] f = new int[N]; // 我们这里只需要记录v                 ，w即可


    




    




    




 ，因为我们会根据输入的数据重新更新v















，w                  ，不再存在s的概念 static int[] v = new int[N]; static int[] w = new int[N]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); // 表示定义到第几个数据 int cnt = 0; // 我们根据输入的数据重新定义v


     



     



     



 ，w for (int i = 1; i <= n; i++) { // a是v














，b是w   
    
    
    
，s是数量 int a = scanner.nextInt(); int b = scanner.nextInt(); int s = scanner.nextInt(); // 我们根据2的k次幂来划分s


     


     


     


，重新分成物品 int k = 1;// 相当于2的0次幂 // 一直更新到无法存放k while ( k <= s){ // 更新数据位置 cnt++; // 将数据存入 v[cnt] = a * k; w[cnt] = b * k; // 数量减去已存放的k 




 




 




 ，并且k翻倍（2次幂） s -= k; k *= 2; } // 判断是否有剩余元素 if (s > 0){ // 若存放剩余元素   

   

   

   
，我们还需要存放 cnt ++; v[cnt] = a * s; w[cnt] = b * s; } } // 我们目前拥有cnt个新物品（被我们分解的） n = cnt; // 我们对新物品进行装载即可（01背包） for (int i = 1; i <= n; i++) { for (int j = m; j >= v[i] ; j--) { f[j] = Math.max(f[j],f[j - v[i]] + w[i]); } } System.out.println(f[m]); } }

分组背包问题

我们首先介绍一下分组背包规则：

/*背包问题*/ 有 N 组物品和一个容量是 V 的背包

   




   




   




 。 每件物品的体积是 vij

     

     

     

，价值是 wij
  




  




  




 ，其中 i 是组号  


  


  


  
，j 是组内编号 



 



 



 
。 求解将哪些物品装入背包 
     
     
     
，可使物品总体积不超过背包容量

   




   




   




 ，且总价值最大,输出最大价值                 。 /*输入格式*/ 第一行有两个整数 N 



 



 



 
，V                 ，用空格隔开


    




    




    




 ，分别表示物品组数和背包容量


    




    




    




 。 接下来有 N 组数据： 每组数据第一行有一个整数 Si















，表示第 i 个物品组的物品数量； 每组数据接下来有 Si 行                  ，每行有两个整数 vij,wij


     



     



     



 ，用空格隔开














，分别表示第 i 个物品组的第 j 个物品的体积和价值； /*输出格式*/ 输出一个整数   
    
    
    
，表示最大价值















。 /*限制条件*/ 每组物品有若干个


     


     


     


，同一组内的物品最多只能选一个                  。

然后我们对其进行分析：

/*内容分析*/ 首先我们有 N 组物品 




 




 




 ，总容量为 V 如果我们想要求得最大 W 的情况   

   

   

   
，我们就需要计算所有的 N组物品中每种物品使用 和 V 情况 /*求解方法分析*/ 我们同样采用一层迭代一层的原则

     

     

     

，但由于每组商品只能选择一次
  




  




  




 ，所以我们在f[i][j]的情况下  


  


  


  
，需要与第i组的所有物品交互判断一次 同样我们由于f[i]只利用f[i-1]层原理 
     
     
     
，我们可以采用滚动数组的原理来将二维数组变为一维数组

我们给出实际代码以及代码中的解析：

/*已优化算法*/ import java.util.Scanner; public class Packsack01 { final static int N = 110; static int n,m; // 这里的f采用一维即可 static int[] f = new int[N]; // 我们这里使用了分组概念

   




   




   




 ，需要二维数组记录信息 static int[][] v = new int[N][N]; static int[][] w = new int[N][N]; // s这里记录该组的个数 static int[] s = new int[N]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); // 对分组输入数据 for (int i = 1; i <= n; i++) { // 记录该组数量 s[i] = scanner.nextInt(); for (int j = 1; j <= s[i]; j++) { // 记录v 



 



 



 
，w v[i][j] = scanner.nextInt(); w[i][j] = scanner.nextInt(); } } // 开始遍历即可 for (int i = 1; i <= n; i++) { for (int j = m; j >= 0; j--) { for (int k = 0;k <= s[i]; k++) { if (v[i][k] <= j){ f[j] = Math.max(f[j],f[j - v[i][k]] + w[i][k]); } } } } System.out.println(f[m]); } }

结束语

好的                 ，关于动态规划篇的背包问题就介绍到这里


    




    




    




 ，希望能为你带来帮助~