程序员的算法课（7）-01背包问题-程序员秋天

一、01背包问题描述

有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

i	1	2	3	4
w(体积)	2	3	4	5
v(价值)	3	4	5	6

二、解法分析

1.分层考虑解决"每个物品最多只能装一次"

每个物品只能装一次,那么就应该想到常用的一种方法,就是用数组的纵轴来解决,对于n个物品,为它赋予i=1~n的编号,那么数组的纵轴就有n层,每层只考虑装不装这个物品,那么分层考虑就可以解决最多装一个的问题了。

2.对0,1的理解

对于每个背包,都只有0和1的情况,也就是拿或者不拿两种情况。
如果拿:那么空间就会减一点,比如说现在在考虑第i个物品拿不拿,如果说当前剩余空间为j,那么拿了之后空间就变为j-c[i],但是总价值却会增加一点,也就是增加w[i]。
如果不拿:那么空间不会变,还是j,但是总价值也不会变化。

3.限制条件

所以对于这题来说有一个限制条件,就是空间不超出,然后目标就是在空间不超出的情况塞入物品使总价值最大。

本问题中最重要的两个值就是物品、背包重量。

4.递归方程的推导

所以定义：m[i][j]表示编号为i的物品、当背包容量为j时的最大可容纳价值。

递归方程：

1、当w[i]>j的时候，说明放不下去，所以肯定不能放i号物品，所以：m[i][j]=m[i-1][j]；
2、当w[i]<=j的时候，说明放的下去，那么问题就是放不放，如果放的话价值是m[i-1][j-w[i]]+v[i]；如果不放下去，就是m[i][j]=m[i-1][j]所以放不放显然取决于两个值的大小；

综上，得到递归方程：

if(j>=w[i])
    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);  
else  
    m[i][j]=m[i-1][j];

因为这里涉及m[i-1][j]，所以递推需要把m[0][j]算出来，然后从1开始递推。m[0][j]比较简单，就是比较w[0]和j的关系。

三、代码实现

/**
 *
 * @param w 物品i的重量为wi
 * @param v 物品i的价值为vi
 * @param c 背包总的容量为c
 * @return 能装入背包的总价值
 */
public static int getResult(int w[], int v[], int c) {
    if(w.length != v.length) {
        throw new IllegalArgumentException();
    }
    if (c <= 0) {
        return 0;
    }
    int n = w.length;
    //m[i][j] 表示 在背包容量剩余j的时候考虑到第i件物品的最大价值（i从0还是计数）
    int m[][] = new int[n][c + 1];

    for(int j = 0; j < c + 1; j++) {
        if(w[0] > j) {
            m[0][j] = 0;
        } else {
            m[0][j] = v[0];
        }
    }

    for(int i = 1; i < n; i++) {
        for(int j = 0; j < c + 1; j++) {
            if(w[i] > j) {
                m[i][j] = m[i - 1][j];
            } else {
                m[i][j] = Math.max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    return m[n - 1][c];
}

四、总结

对于01背包问题，用蛮力法与用动态规划解决得到的最优解和解组成是一致的，所以动态规划解决此类问题是可行的。动态规划效率为线性，蛮力法效率为指数型，结合以上内容和理论知识可以得出，解决此问题用动态规划比用蛮力法适合得多。对于动态规划不足的是空间开销大，数据的存储得用到二维数组；好的是，当前问题的解只与上一层的子问题的解相关，所以，可以把动态规划的空间进行优化，使得空间效率从O(n*c)转化为O(c)，遗憾的是，虽然优化了空间，但优化后只能求出最优解，解组成的探索方式在该方法运行的时候已经被破坏掉；总之动态规划和优化后的动态规划各有优缺点，可以根据实际问题的需求选择不同的方式。

我的微信公众号：架构真经（id：gentoo666），分享Java干货，高并发编程，热门技术教程，微服务及分布式技术，架构设计，区块链技术，人工智能，大数据，Java面试题，以及前沿热门资讯等。每日更新哦！

参考资料：

1、 https://www.jianshu.com/p/cb5957344256；
2、 https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html；
3、 https://www.cnblogs.com/zyacmer/p/9961710.html；
4、 https://www.jianshu.com/p/b0376bc3cd76；