经典动态规划：0-1 背包问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：经典动态规划：0-1 背包问题

评论礼仪 见这里，违者直接拉黑。

[xiaoyu-wen-1118]

能给出leetcode题号，实操一下吗

[zhao-hang-yu]

416 494 1049 474

[junjiezou1]

https://www.acwing.com/problem/content/2/

[labuladong]

这篇文章力扣没有对应题目

[yangyj1994]

而 dp[i-1][w - wt[i-1]] 也很好理解：你如果装了第 i 个物品，就要寻求剩余重量 w - wt[i-1] 限制下的最大价值，加上第 i 个物品的价值 val[i-1]。

--amazing。如果背包载重为5，前面已经装过数种方案。。假如这时要装的物品重量为2，那么之前的方案只能选重量为3时的最大化方案【不要考虑没有物品重量加起来是否刚好可以等于3，因为在w为3的情况下，也已经过了一遍最大化方案，假如只有重量为2的物品，那么重量相加不可能等于3,3的场景最大化收益就等于2的最大化收益【2 + 2 装不进背包，只能丢掉，只能取2的最大化收益】】。

[mujojowang]

为什么把n放在外层循环把w放在内层循环？怎么判断状态的顺序？

[Anan121no]

蓝桥杯里有这题

[Jebearssica]

遍历范围如果精确一下的话，似乎就不需要额外判断装不下的情况（索引溢出）

for (int w = wt[i]; w <= W; w++)

[DapengJin]

这两个都是 0-1 背包的题呀
494. Target Sum
416. Partition Equal Subset Sum

[GXhunter]

原汁原味的01背包在牛客 https://www.nowcoder.com/questionTerminal/708f0442863a46279cce582c4f508658?

[labuladong]

@DapengJin 这两个是背包问题，但不是 0-1 背包，我都有写过的

[Tokics]

题目中的： 其中第 i 个物品的重量为 wt[i]，价值为 val[i]
和分析中的： 由于 i 是从 1 开始的，所以 val 和 wt 的索引是 i-1 时表示第 i 个物品的价值和重量。

是不是有点矛盾啊？

[labuladong]

@Tokics 感谢指出，我表述的有点模糊，已修改

[zijunchen68]

其实这个模版W的枚举方向错了，变成完全背包问题了
可以看一下用例
背包W = 100，种类数量为1
w[0] = 1, val[0] = 1000

[Maxiah]

东哥我想问一下这里装入的情况为什么不像01背包问题的状态转移方程一样使用dp[i-1][j-nums[i-1]]+nums[i]呢？

dp[i][j] = dp[i - 1][j] || dp[i-1][j-nums[i-1]];
//              不装入          装入

[chenchanglong1997]

这地方是有一个bug的，需要对wt进行一个排序

[ArisAachen]

确实有这个问题
简单的测试一下

    std::vector<int> weight_vec {2, 1, 3};
    std::vector<int> value_vec {4, 2, 3};
    knapsack(1, 1, weight_vec, value_vec);

[labuladong]

解法没问题，你这个测试是错的。N 的值必须等于 wt 数组的长度，也就是说在你的例子中应该调用 knapsack(1, 3, weight_vec, value_vec)，这样就没问题了。

[yonggui-yan]

打卡。

[NIKEmissa]

“dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，...”在定义这里，w是不是可以理解为背包当前的负载？

[labuladong]

不是负载，应该理解为空闲空间

[cool-hacker00]

应该不是空闲把，应该是总的背包空间

[morganwu277]

w表示背包限重，即当前物品，总重量不超过w。根据不同的子问题，会变化。

[GXhunter]

力扣没有对应的题目，但牛客有：https://www.nowcoder.com/questionTerminal/708f0442863a46279cce582c4f508658?

import java.util.Scanner;
public class Main {
    /**
     * @param w 物件重量
     * @param v 物件价值
     * @param C 背包容量
     * @return
     */
    public int knapsack01(int[] w, int[] v, int C) {
//        物件个数
        int n = w.length;
//        dp[i][j]: 使用容量i的背包，装前j个物品，最大收益
        int[][] dp = new int[C + 1][n];
//        转移方程 dp[i][j] = max{ dp[i-w[j]][j-1], dp[i][j-1] }
        for (int i = 0; i <= C; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (j == 0) {
                    dp[i][0] = i >= w[j] ? v[j] : 0;
                    continue;
                }
                if (i >= w[j]) {
//                    可以看出只和上方和左边有关系，所以C和n哪个循环在外无关系
                    dp[i][j] = Math.max(dp[i - w[j]][j - 1] + v[j], dp[i][j - 1]);
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[C][n - 1];
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int C = scanner.nextInt();
        int n = scanner.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
        System.out.println(new Main().knapsack01(w, v, C));
    }
}

[zjthappy]

// 01背包
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
  int V,N;
  int value[1001];
  int volume[1001];
  cin>>V>>N;
  for(int i=1;i<=N;i++){
    cin>>volume[i]>>value[i];
  }

  // 定义dp数组 采用自底向上 迭代 
  // dp[i][j]是前i个物品，背包容量是j的时候的最大价值
  // 目标就是求dp[N][V]
  vector<vector<int>>dp(N+1,vector<int>(V+1,0));
  for(int i=1;i<=N;i++){
    for(int j=1;j<=V;j++){
       
      // 如果第i个物品无法装入 直接
      if(j<volume[i]){
        dp[i][j] = dp[i-1][j];
  
      }
      // 可以选择 装当前物品 或者 不装当前物品
      else{
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]);
      }
        
    }
  }

  cout<<dp[N][V]<<endl;
}

[gaosh96]

牛客上原版的 0-1背包 问题

https://www.nowcoder.com/questionTerminal/708f0442863a46279cce582c4f508658

把 wt 数组和 val 数组都声明为 n+1，物品编号和重量、价值都根据 index 一一对应，这样后面的j - wt[i]和val[i]不用再考虑 -1 的问题，便于处理。

另外声明成 int[][] dp = new int[n + 1][w + 1];相当于直接把 base case也声明了。

如果w从 0 开始遍历，在重量上就会有问题，重量区间是 [1, w]，不是 [0, w]

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int w = in.nextInt();
        int n = in.nextInt();

        int[] wt = new int[n + 1];
        int[] val = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            wt[i] = in.nextInt();
            val[i] = in.nextInt();
        }

        int maxVal = getMaxVal(n, w, wt, val);
        System.out.println(maxVal);
    }

    private static int getMaxVal(int n, int w, int[] wt, int[] val) {
        int[][] dp = new int[n + 1][w + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w; j++) {
                if (j - wt[i] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wt[i]] + val[i]);
                }
            }
        }

        return dp[n][w];
    }

}

[CarlLy7]

打卡

[marmot-z]

怎么用递归（从上至下）的方式实现呢？

[marmot-z]

只能先理解递归的实现才会改写成迭代实现，怎么办😰

/**
     * w 容量背包能装下最大的物品价值
     *
     * @param w 包容量
     * @param n n 个物品（n == wt.len）
     * @param wt 物品质量
     * @param val 物品价值
     * @return
     */
    public int knapsack(int w, int n, int[] wt, int[] val) {
        int[][] memo = new int[w + 1][n];
        for (int i = 0; i <= w; i++) {
            Arrays.fill(memo[i], -1);
        }

        return dp(w, 0, wt, val, memo);
    }

    /**
     * w 包容量下从 [i, wt.len - 1] 物品中挑选能装下的最大物品价值
     */
    private int dp(int w, int i, int[] wt, int[] val, int[][] memo) {
        // 背包无剩余容量，可装物品价值为 0
        if (w <= 0) return 0;
        // 无物品进行装填，可装物品价值为 0
        if (i == wt.length) return 0;

        if (memo[w][i] != -1) {
            return memo[w][i];
        }

        int result;
        // 当前物品大于背包容量，不进行装填
        if (wt[i] > w) {
            result = dp(w, i + 1, wt, val, memo);
        } else {
            result = Math.max(
                    // 不装填物品 i
                    dp(w, i + 1, wt, val, memo),
                    // 装填物品 i，价值 +val[i]，背包容量 -wt[i]
                    val[i] + dp(w - wt[i], i + 1, wt, val, memo)
            );
        }

        return memo[w][i] = result;
    }

[zenyanggongmian1995]

新手入门，这句表述我有一些困惑：你如果选择将第 i 个物品装进背包，那么第 i 个物品的价值 val[i-1] 肯定就到手了，接下来你就要在剩余容量 w - wt[i-1] 的限制下，在前 i - 1 个物品中挑选，求最大价值，即 dp[i-1][w - wt[i-1]]。 我理解上这是一个二维动态表，每次填表依赖的是左和上，而不是在 '在前i-1个物品中挑选'？

[realRuiGuo]

// 验证按照0-1背包定义也能解决。dp数组含义是能放入的最大重量，如果dp[n][w]重量刚好为总和的一半，就表示能分成两组满足各一半。
class Solution {
public:
bool canPartition(vector &nums) {
int sum = 0;
int n = nums.size();
for (auto &item: nums) {
sum += item;
}
if (sum % 2 != 0) {
return false;
}
int w = sum / 2;
vector<vector> dp(n + 1, vector(w + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (j - nums[i - 1] < 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j - nums[i - 1]] + nums[i - 1], dp[i - 1][j]);
}
}
}
return (dp[n][w] == w);
}
};