https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

视频讲解：https://www.bilibili.com/video/BV1cg411g7Y6

1.01背包问题我一直觉得其实挺难的，无论是dp数组的初始化还是递归公式的推导，我初次接触这个题的时候是真的没办法快速理解的，最难的我觉得就是对于dp数组的定义，这个含义是贯穿整个题最重要的部分，要在理解含义的基础上才能完成下面的问题。

CPP

#include<bits/stdc++.h>
using namespace std;

int main(){
    int M, N;
    cin>>M>>N;
    vector<int> space(M, 0);
    vector<int> value(M, 0);
    for(int i = 0; i < M; i++){
        cin>>space[i];
    }  
    for(int i = 0; i < M; i++){
        cin>>value[i];
    }
    vector<vector<int>> dp(M, vector<int>(N + 1, 0));
    for(int j = space[0]; j <= N; j++){
        dp[0][j] = value[0]; 
    }
    
    for(int i = 1; i < M; i++){
        for(int j = 1; j <= N; j++){
            if(j < space[i])dp[i][j] = dp[i - 1][j];
            else{
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - space[i]] + value[i]);
                
            }
        }
    }
    cout <<dp[M - 1][N];
    return 0;
}