二维数组DP

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

const int N=1005;
int n,m;
int v[N], w[N];
int f[N][N];

int main(){
    memset(f, 0x00, sizeof f); // f[i][j]表示前i个物品体积不超过j的最大价值
    cin>>n>>m;
    for(int i=1; i<=n; ++i) cin>>v[i]>>w[i];

    for(int i=1; i<=n; ++i)
        for(int j=0; j<=m; ++j){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j], f[i][j-v[i]]+w[i]);
        }
    cout<<f[n][m]<<endl;

    return 0;

}

一维数组优化

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

const int N=1005;
int n,m;
int v[N], w[N];
int f[N];

int main(){
    memset(f, 0x00, sizeof f); // f[i][j]表示前i个物品体积不超过j的最大价值
    cin>>n>>m;
    for(int i=1; i<=n; ++i) cin>>v[i]>>w[i];

    for(int i=1; i<=n; ++i)
        for(int j=v[i]; j<=m; ++j)
            f[j]=max(f[j], f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;

    return 0;

}