动态规划之背包问题

关注顶级算法修炼内功

顶级算法后台回复 1024 有特别礼包

责编：顶级算法 | 来源：_code_x

链接：jianshu.com/p/b789ec845641

上一篇精彩：一位大佬用了“算法刷题宝典.pdf”，进阿里了......

大家好，我是顶级算法。

写在前

问题描述

有N件物品和一个最多能被重量为W 的背包。一个物品只有两个属性：重量和价值。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。扩展：一位大佬用了“算法刷题宝典”，进阿里了......

注意：0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。

基本思路

这里有两个可变量体积和价值，我们定义dp[i][j]表示前i件物品体积不超过j能达到的最大价值，设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

另外，搜索公众号技术社区后台回复“算法”，获取一份惊喜礼包。

• 第 i 件物品没添加到背包，最大价值：dp[i][j] = dp[i - 1][j]。

• 第 i 件物品添加到背包中：dp[i][j] = dp[i - 1][j - w] + v。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

代码实现

// W 为背包总重量
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
    // dp[i][0]和dp[0][j]没有价值已经初始化0
    int[][] dp = new int[N + 1][W + 1];
    // 从dp[1][1]开始遍历填表
    for (int i = 1; i <= N; ++i) {
        // 第i件物品的重量和价值 
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; ++j) {
            if (j < w) {
                // 超过当前状态能装下的重量j
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }
    return dp[N][W];
}

dp[i][j]的值只与dp[i-1][0,...,j-1]有关，所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）。因此，0-1 背包的状态转移方程为：dp[j] = max(dp[j], dp[j - w] + v)

特别注意：为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向遍历。优化空间复杂度：

ps:滚动数组：即让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。

public int knapsack(int W, int N, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = W; j >= 1; --j) {
            if (j >= w) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
    }
    return dp[W];
}

ps：01背包内循环理解：还原成二维的dp就很好理解，一维的dp是二维dp在空间上进行复用的结果。dp[i]=f(dp[i-num])，等式的右边其实是二维dp上一行的数据，应该是只读的，在被读取前不应该被修改。如果正序的话，靠后的元素在读取前右边的dp有可能被修改了，倒序可以避免读取前被修改的问题。

排序序列：
1、程序员必知必会的排序一：冒泡排序2、程序员必知必会的排序二：快速排序3、程序员必知必会的排序三：直接插入排序4、程序员必知必会的排序四：希尔排序5、程序员必知必会的排序五：拓扑排序6、程序员必知必会的排序六：选择排序7、程序员必知必会的排序七：归并排序8、程序员必知必会的排序八：基数排序9、程序员必知必会的排序九：堆排序

觉得不错？欢迎转发分享给更多人

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 10T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！

👆扫码回复【面试题】即可获取👆

公众号后台回复 算法 或者 算法心得 有惊喜礼包！顶级算法交流群

 「顶级算法」建立了读者算法交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。

扫描添加好友邀你进算法群，加我时注明【姓名+公司+职位】

版权申明：内容来源网络，版权归原作者所有。如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。

往日分享：