算法题之动态规划-01背包问题_数据结构与算法-IT乾坤技术博客

### 文字介绍解决背包问题
假设山洞里共有a,b,c,d ,e这5件宝物（不是5种宝物），它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。

此时只要理解了状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),  f[i-1,j] }，就知道这道算法的答案了，这个状态转换方程是怎么来的呢？往下看

```sql 
 假如背包要放第i件物品，此时如果不放第i件物品，那么问题就转化为“前i-1件物品放入重量是w的背包中”，价值为f[i-1,j]；
 如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的重量为j-Wi的背包中”，此时能获得的最大价值就是f[i-1,j-Wi]
 再加上通过放入第i件物品获得的价值Pi，此时只要比较f[i-1,j]和f[i-1,j-Wi]+Pi那个大就能获取到背包里最大的价值是多少了。
```

可能还是不是太懂，那么我们看图来理解，这里就使用大佬的图片了，就是下面的图片，有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，怎么获取价值最大的背包呢 
![在这里插入图片描述](https://itqiankun.oss-cn-beijing.aliyuncs.com/picture/2019-8-4/20190724183559279.png)

首先对这个图片要知道的是：

- 明确这张表是至底向上，从左到右生成的。
- 然后用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。
- 对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。
- 同理，c2=0，b2=3,a2=6。

对于承重为8的背包，a8=15,是怎么得出的呢？根据01背包的状态转换方程，需要考察两个值，就是下面的两个
- 一个是f[i-1,j]，这种情况就是承重为8的背包里面不放a这个物品这一种情况(根据上面的状态转换方程来的)，这里i就是下面的横列的值，然后j就是指竖列的值，所以此时f[i-1,j]里面的i就是a、j就是8，因为a的下一列是b，所以f[i-1,j]就是指b8，所以此时的f[i-1,j]的值就是9

- 另一个是f[i-1,j-Wi]+Pi，这种情况就是承重为8的背包里面要放a这个物品这一种情况(根据上面的状态转换方程来的)，既然要放a这个物品，那么此时的Pi的值就是6(因为a商品的价值是6)，然后因为承重为8的背包里面已经确定要放a这个物品，所以此时这个背包里面最多还只能存放的重量就是6，这里i就是下面的横列的值，然后j就是指竖列的值，所以此时f[i-1,j-Wi]里面的i就是a、j就是8、Wi就是2(这个2就是a物品的重量)，所以此时f[i-1,j-Wi]就是指b6，此时b6的值是9，所以f[i-1,j-Wi]+Pi=9+6=15，所以物品a应该放入称重是8的背包里面

### java代码解答这个背包问题

下面的红色代码注释里面的数组里面的第一个索引都是0，这是为了避免数组的0索引问题

下面的蓝色代码注释里面的for循环目的就是为了创建 这样的一个图片![在这里插入图片描述](https://itqiankun.oss-cn-beijing.aliyuncs.com/picture/2019-8-4/20190724183559279.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY4OTQ4MA==,size_16,color_FFFFFF,t_70)，然后只要创建好上面的图片，那么我们就能知道背包问题的答案了

```java
package com.one.util;

public class Test {
    public static int getMaxValue(int[] weight, int[] value, int w, int n) {
        int[][] table = new int[n + 1][w + 1];// 创建一个二维数组，横列是物品的价值，竖列是物品的重量
        // 蓝色代码注释开始
        for (int i = 1; i <= n; i++) { //物品
            for (int j = 1; j <= w; j++) {  //背包大小
                if (weight[i] > j) {
                    //当前物品i的重量比背包容量j大，装不下，肯定就是不装
                    table[i][j] = table[i - 1][j];
                } else { //装得下，Max{装物品i， 不装物品i}
                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        // 蓝色代码注释结束
        return table[n][w];
    }

public static void main(String[] args) {
        int n = 5, w = 10;                    //物品个数，背包容量
        // 红色代码注释开始
        int[] value = {0,6, 3, 5, 4, 6};     //各个物品的价值
        int[] weight = {0,2, 2, 6, 5, 4};    //各个物品的重量
        // 红色代码注释结束
        System.out.println(getMaxValue(weight, value, w, n));
    }
}
```

大佬网址
https://blog.csdn.net/evillist/article/details/74455044 
https://www.kancloud.cn/kancloud/pack/70125 
https://blog.csdn.net/mu399/article/details/7722810

算法题之动态规划-01背包问题

全部教程