背包问题_概述(动态规划)

背包问题_概述(动态规划)

写在前 image.png 问题描述 有N件物品和一个最多能被重量为W 的背包。一个物品只有两个属性:重量和价值。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 注意:0-1 背包问题无法使用贪...

写在前

image.png

问题描述

有N件物品和一个最多能被重量为W 的背包。一个物品只有两个属性:重量和价值。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

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

image.png

基本思路

这里有两个可变量体积和价值,我们定义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 

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 = 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有可能被修改了,倒序可以避免读取前被修改的问题。

文章来源于互联网:背包问题_概述(动态规划)

0

评论0

鱼翔浅底,鹰击长空,驼走大漠
没有账号? 注册  忘记密码?