程序员的算法课(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

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: