链接：https://kamacoder.com/problempage.php?pid=1046

题目描述：

方法1：二维dp解决背包问题

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int solve(int M,int N,vector<int> weight,vector<int> value){
    vector<vector<int>>dp(M,vector<int>(N+1,0));
    for(int i=weight[0];i<=N;i++) dp[0][i] = value[0];//初始化dp数组
    
    for(int i=1;i<M;i++){
        for(int j=1;j<=N;j++){//更新dp数组
            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]);//装得下
        }
    }
    return dp[M-1][N];
}

int main(){
    int M,N;
    cin>>M>>N;
    vector<int>weight(M,0);
    vector<int>value(M,0);
    for(int i=0;i<M;i++){
        cin>>weight[i];
    }
    for(int i=0;i<M;i++){
        cin>>value[i];
    }
    
    int max_value = solve(M,N,weight,value);
    cout<<max_value<<endl;
    return 0;
}

方法二：改为一维dp数组，使用滚动数组的思想

注：采用倒序遍历

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int solve(int M,int N,vector<int> weight,vector<int> value){
    vector<int> dp(N+1,0);
    for(int i=weight[0];i<=N;i++) dp[i] = value[0];//初始化第一行数据
    
    for(int i=1;i<M;i++){
        for(int j=N;j>=weight[i];j--){//倒叙遍历更新数组
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    return dp[N];
}

int main(){
    int M,N;
    cin>>M>>N;
    vector<int>weight(M,0);
    vector<int>value(M,0);
    for(int i=0;i<M;i++){
        cin>>weight[i];
    }
    for(int i=0;i<M;i++){
        cin>>value[i];
    }
    
    int max_value = solve(M,N,weight,value);
    cout<<max_value<<endl;
    return 0;
}