第一次做这题确实没什么思路，看了卡哥的视频也是似懂非懂，现在整理一下。
首先明确变量有哪些，物品种类，单个物品重量，单个物品价值，背包的最大容量容量；这些变量该如何融入递推公式中呢？
先明确题目所求的是什么，在背包容纳范围下的价值最大。
为了求容量空间为N的价值最大，可以推想容量空间为1，为2该怎么求？
单个物品重量，单个物品价值其实是包含在物品种类这个变量中的。
综合所有变量，我们可以确定dp[i][j]。i就是表示物品种类，j就是背包最大容量。
这二维dp数组就像之前leetcode所有路径那道题了。
先初识化，确定第一行，第一列。
再确定递推公式，
// 如果装不下这个物品,那么就继承dp[i - 1][j]的值
// 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值
// 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 + 该物品的价值构成
点击查看代码
if (j < spa[i]) dp[i][j] = dp[i - 1][j];
else{
int num1=dp[i-1][j];
int num2=dp[i-1][j-spa[i]]+val[i];
dp[i][j]=max(num1,num2);}
}
卡哥强调了这个遍历顺序，这道题先遍历背包或先遍历物品都可以。可以画出这图看清楚。
当前的值要么从上方来，要么从左上角来，两种遍历画图可知这几个地方都有值，因此都可以。
完整代码：
点击查看代码
#include<iostream>
#include<vector>
using namespace std;
int main(){
int kind;int space;
cin>>kind>>space;
vector<int>spa;
vector<int>val;
for(int i=0;i<kind;i++){
int num;
cin>>num;
spa.push_back(num);
}
for(int i=0;i<kind;i++){
int num;
cin>>num;
val.push_back(num);
}
vector<vector<int>> dp(kind, vector<int>(space + 1, 0));
for(int j=spa[0];j<=space;j++){
dp[0][j]=val[0];
}
for(int i=1;i<kind;i++){
for(int j=0;j<=space;j++){
if (j < spa[i]) dp[i][j] = dp[i - 1][j];
else{
int num1=dp[i-1][j];
int num2=dp[i-1][j-spa[i]]+val[i];
dp[i][j]=max(num1,num2);}
}
}
cout<<dp[kind-1][space];
return 0;
}