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-2.html

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

1.本题将是背包问题使用滑动一维数组的方法，其实我是觉得没有二维那么好理解，因为二维我使用的是一个表格我在脑海里模拟表格即可很好的理解整个迭代公式，已经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;
    
    
    vector<int> dp(N + 1, 0);
    for(int i = 0; i < M; i++){
        for(int j = N; j >= space[i]; j--){
            dp[j] = max(dp[j], dp[j - space[i]] + value[i]);
        }
    }
    std::cout << dp[N] << std::endl;
    return 0;
}