参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！
本题力扣上没有原题，大家可以去卡码网第46题去练习，题意是一样的。
《代码随想录》算法视频公开课：带你学透0-1背包问题！，相信结合视频再看本篇题解，更有助于大家对本题的理解。
正式开始讲解背包问题！
对于面试的话，其实掌握01背包和完全背包，就够用了，最多可以再来一个多重背包。
如果这几种背包，分不清，我这里画了一个图，如下：
除此以外其他类型的背包，面试几乎不会问，都是竞赛级别的了，leetcode上连多重背包的题目都没有，所以题库也告诉我们，01背包和完全背包就够用了。
而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。
所以背包问题的理论基础重中之重是01背包，一定要理解透！
leetcode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题。
所以我先通过纯01背包问题，把01背包原理讲清楚，后续再讲解leetcode题目的时候，重点就是讲解如何转化为01背包问题了。
之前可能有些录友已经可以熟练写出背包了，但只要把这个文章仔细看完，相信你会意外收获！
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。
这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？
每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！
在下面的讲解中，我举一个例子：
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
问背包能背的物品最大价值是多少？
以下讲解和图示中出现的数字都是以这个例子为例。
（为了方便表述，下面描述 统一用 容量为XX的背包，放下容量（重量）为XX的物品，物品的价值是XX）
依然动规五部曲分析一波。
- 确定dp数组以及下标的含义
我们需要使用二维数组，为什么呢？
因为有两个维度需要分别表示：物品 和 背包容量
如图，二维数组为 dp[i][j]。
那么这里 i 、j、dp[i][j] 分别表示什么呢？
i 来表示物品、j表示背包容量。
（如果想用j 表示物品，i 表示背包容量 行不行？ 都可以的，个人习惯而已）
我们来尝试把上面的 二维表格填写一下。
动态规划的思路是根据子问题的求解推导出整体的最优解。
我们先看把物品0 放入背包的情况：
背包容量为0，放不下物品0，此时背包里的价值为0。
背包容量为1，可以放下物品0，此时背包里的价值为15.
背包容量为2，依然可以放下物品0 （注意 01背包里物品只有一个），此时背包里的价值为15。
以此类推。
再看把物品1 放入背包：
背包容量为 0，放不下物品0 或者物品1，此时背包里的价值为0。
背包容量为 1，只能放下物品0，背包里的价值为15。
背包容量为 2，只能放下物品0，背包里的价值为15。
背包容量为 3，上一行同一状态，背包只能放物品0，这次也可以选择物品1了，背包可以放物品1 或者 物品0，物品1价值更大，背包里的价值为20。
背包容量为 4，上一行同一状态，背包只能放物品0，这次也可以选择物品1了，背包可以放下物品0 和 物品1，背包价值为35。
以上举例，是比较容易看懂，我主要是通过这个例子，来帮助大家明确dp数组的含义。
上图中，我们看 dp[1][4] 表示什么意思呢。
任取 物品0，物品1 放进容量为4的背包里，最大价值是 dp[1][4]。
通过这个举例，我们来进一步明确dp数组的含义。
即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的，如果哪里看懵了，就来回顾一下i代表什么，j又代表什么。
- 确定递推公式
这里在把基本信息给出来：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
对于递推公式，首先我们要明确有哪些方向可以推导出 dp[i][j]。
这里我们dp[1][4]的状态来举例：
求取 dp[1][4] 有两种情况：
- 放物品1
- 还是不放物品1
如果不放物品1， 那么背包的价值应该是 dp[0][4] 即 容量为4的背包，只放物品0的情况。
推导方向如图：
如果放物品1， 那么背包要先留出物品1的容量，目前容量是4，物品1 的容量（就是物品1的重量）为3，此时背包剩下容量为1。
容量为1，只考虑放物品0 的最大价值是 dp[0][1]，这个值我们之前就计算过。
所以 放物品1 的情况 = dp[0][1] + 物品1 的价值，推导方向如图：
两种情况，分别是放物品1 和 不放物品1，我们要取最大值（毕竟求的是最大价值）
dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的价值)
以上过程，抽象化如下：
-
不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
-
放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- dp数组如何初始化
关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：
在看其他情况。
状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
代码初始化如下：
for (int j = 0 ; j < weight[0]; j++) { // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}此时dp数组初始化情况如图所示：
dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢？
其实从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。
初始-1，初始-2，初始100，都可以！
但只不过一开始就统一把dp数组统一初始为0，更方便一些。
如图：
最后初始化代码如下：
// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
费了这么大的功夫，才把如何初始化讲清楚，相信不少同学平时初始化dp数组是凭感觉来的，但有时候感觉是不靠谱的。
- 确定遍历顺序
在如下图中，可以看出，有两个遍历的维度：物品与背包重量
那么问题来了，先遍历 物品还是先遍历背包重量呢？
其实都可以！！ 但是先遍历物品更好理解。
那么我先给出先遍历物品，然后遍历背包重量的代码。
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）
例如这样：
// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
for(int i = 1; i < weight.size(); i++) { // 遍历物品
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}为什么也是可以的呢？
要理解递归的本质和递推的方向。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程如图所示：
再来看看先遍历背包，再遍历物品呢，如图：
大家可以看出，虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！
但先遍历物品再遍历背包这个顺序更好理解。
其实背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。
- 举例推导dp数组
来看一下对应的dp数组的数值，如图：
最终结果就是dp[2][4]。
建议大家此时自己在纸上推导一遍，看看dp数组里每一个数值是不是这样的。
做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！
很多同学做dp题目，遇到各种问题，然后凭感觉东改改西改改，怎么改都不对，或者稀里糊涂就改过了。
主要就是自己没有动手推导一下dp数组的演变过程，如果推导明白了，代码写出来就算有问题，只要把dp数组打印出来，对比一下和自己推导的有什么差异，很快就可以发现问题了。
本题力扣上没有原题，大家可以去卡码网第46题去练习，题意是一样的，代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, bagweight;// bagweight代表行李箱空间
cin >> n >> bagweight;
vector<int> weight(n, 0); // 存储每件物品所占空间
vector<int> value(n, 0); // 存储每件物品价值
for(int i = 0; i < n; ++i) {
cin >> weight[i];
}
for(int j = 0; j < n; ++j) {
cin >> value[j];
}
// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化, 因为需要用到dp[i - 1]的值
// j < weight[0]已在上方被初始化为0
// j >= weight[0]的值就初始化为value[0]
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
for(int i = 1; i < weight.size(); i++) { // 遍历科研物品
for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
cout << dp[n - 1][bagweight] << endl;
return 0;
}
背包问题 是动态规划里的经典类型题目，大家要细细品味。
可能有的同学并没有注意到初始化 和 遍历顺序的重要性，我们后面做力扣上背包面试题目的时候，大家就会感受出来了。
下一篇 还是理论基础，我们再来讲一维dp数组实现的01背包（滚动数组），分析一下和二维有什么区别，在初始化和遍历顺序上又有什么差异。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int bagweight = scanner.nextInt();
int[] weight = new int[n];
int[] value = new int[n];
for (int i = 0; i < n; ++i) {
weight[i] = scanner.nextInt();
}
for (int j = 0; j < n; ++j) {
value[j] = scanner.nextInt();
}
int[][] dp = new int[n][bagweight + 1];
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= bagweight; j++) {
if (j < weight[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
System.out.println(dp[n - 1][bagweight]);
}
}n, bagweight = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
dp = [[0] * (bagweight + 1) for _ in range(n)]
for j in range(weight[0], bagweight + 1):
dp[0][j] = value[0]
for i in range(1, n):
for j in range(bagweight + 1):
if j < weight[i]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
print(dp[n - 1][bagweight])package main
import (
"fmt"
)
func main() {
var n, bagweight int // bagweight代表行李箱空间
fmt.Scan(&n, &bagweight)
weight := make([]int, n) // 存储每件物品所占空间
value := make([]int, n) // 存储每件物品价值
for i := 0; i < n; i++ {
fmt.Scan(&weight[i])
}
for j := 0; j < n; j++ {
fmt.Scan(&value[j])
}
// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, bagweight + 1)
}
// 初始化, 因为需要用到dp[i - 1]的值
// j < weight[0]已在上方被初始化为0
// j >= weight[0]的值就初始化为value[0]
for j := weight[0]; j <= bagweight; j++ {
dp[0][j] = value[0]
}
for i := 1; i < n; i++ { // 遍历科研物品
for j := 0; j <= bagweight; j++ { // 遍历行李箱容量
if j < weight[i] {
dp[i][j] = dp[i-1][j] // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
}
}
}
fmt.Println(dp[n-1][bagweight])
}
func max(x, y int) int {
if x > y {
return x
}
return y
}const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
let input = [];
readline.on('line', (line) => {
input.push(line);
});
readline.on('close', () => {
let [n, bagweight] = input[0].split(' ').map(Number);
let weight = input[1].split(' ').map(Number);
let value = input[2].split(' ').map(Number);
let dp = Array.from({ length: n }, () => Array(bagweight + 1).fill(0));
for (let j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
for (let i = 1; i < n; i++) {
for (let j = 0; j <= bagweight; j++) {
if (j < weight[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
console.log(dp[n - 1][bagweight]);
});#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, bagweight;
scanf("%d %d", &n, &bagweight);
int *weight = (int *)malloc(n * sizeof(int));
int *value = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
scanf("%d", &weight[i]);
}
for (int j = 0; j < n; ++j) {
scanf("%d", &value[j]);
}
int **dp = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; ++i) {
dp[i] = (int *)malloc((bagweight + 1) * sizeof(int));
for (int j = 0; j <= bagweight; ++j) {
dp[i][j] = 0;
}
}
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= bagweight; j++) {
if (j < weight[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
printf("%d\n", dp[n - 1][bagweight]);
for (int i = 0; i < n; ++i) {
free(dp[i]);
}
free(dp);
free(weight);
free(value);
return 0;
}
