动态规划篇——背包问题

动态规划篇——背包问题

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

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

背包问题概述

背包问题算是很经典的动态规划问题，我们在面试中也经常出现
首先我们给出动态规划的思想：

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

1. /*背包问题*/
3. 有 N 件物品和一个容量是 V 的背包。
5. 第 i 件物品的体积是 vi，价值是 wi。
7. 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。
9. /*输入格式*/
10.    
11. 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
13. 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
15. /*输出格式*/
16.    
17. 输出一个整数，表示最大价值。

复制代码

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

1. /*01背包问题*/
3. 每件物品只能使用一次
4.    
5. /*完全背包问题*/
6.    
7. 每件物品无次数限制使用
8.    
9. /*多重背包问题*/
10.    
11. 每件物品有不同的使用次数
12.    
13. /*分组背包问题*/
14.    
15. 每组物品有若干个，同一组内的物品最多只能选一个

复制代码

零一背包问题

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

1. /*背包问题*/
3. 有 N 件物品和一个容量是 V 的背包。
5. 第 i 件物品的体积是 vi，价值是 wi。
7. 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。
9. /*输入格式*/
10.    
11. 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
13. 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
15. /*输出格式*/
16.    
17. 输出一个整数，表示最大价值。    /*限制条件*/    每件物品只能使用一次

复制代码

然后我们对其进行分析：

1. /*内容分析*/
3. 首先我们有 N 件物品，总容量为 V
4.    
5. 如果我们想要求得最大 W 的情况，我们就需要计算所有的 N 和 V 情况
6.    
7. /*暴力求解方法分析*/
8.    
9. 我们这里首先采用最暴力的方法（二维）：
10.    
11. 我们采用f[i][j]来表示前i件物品中进行选择，其体积不超过j，储存值为W最优解
12.    
13. 我们会发现，f[i][j]无非就两种情况：
14.     在i比前一位增加一位后，如果我们当前的i没有包含最后一位，那么一切都和上一位i的结果相同（f[i][j] = f[i-1][j]）
15.     那么我们就只需要判断是否需要加上第i位，且前提是j >= v[i]（f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i])）
16.            
17. /*优化方法分析*/
19. 下面我们介绍的优化方法来自于滚动数组：
20.     滚动数组是指当我们只需要两行数据时，我们可以抛出二维的概念，采用层级差来覆盖掉之前的数据信息，从而转换为一维
21.    
22. 我们对上述暴力求解进行分析：
23.     我们会发现其实我们所采用的无非只有两行：f[i]和f[i-1]
24.     那么我们只需要将f[i]所使用的f[i-1]的信息在使用前保留下来，我们就可以将其简化为一行,也就是一维

复制代码

我们给出实际代码以及代码中的解析：
[code]/*暴力求解方法*/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