二维数组

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N, V;
    cin>>N>>V;
    int Vol[N+1]; // 体积
    int Val[N+1]; // 价值
    memset(Vol, 0x00, sizeof Vol);
    memset(Val, 0x00, sizeof Val);
    for(int i=1; i<=N; ++i){
        cin>>Vol[i]>>Val[i];
    }

    // dp求解背包问题
    // 定义f[i][j]表示i个物品拼出体积j时的最大价值
    // 转移方程 f[i][j] = max(f[i-1][j], f[i-1][j-vi]+wi), 在不装第i个物品和装入第i个物品中选取最大值
    int f[N+1][V+1];
    memset(f, 0x00, sizeof f);

    int maxV=0; // 记录背包装载的最大价值

    // 对物品序号和背包容量进行枚举
    for(int i=1; i<=N; ++i){
        for(int j=0; j<=V; ++j){
            if(j>=Vol[i]) f[i][j]=max(f[i-1][j], f[i-1][j-Vol[i]]+Val[i]); // 如果可以装载新物品, 取最大价值
            else f[i][j] = f[i-1][j]; // 如果不可以装载新物品, 则保持原来价值
            maxV = max(maxV, f[i][j]);// 更新背包物品的最大价值
        }
    }

    cout<<maxV<<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(v, 0x00, sizeof v);
    memset(w, 0x00, sizeof w);
    memset(f, 0x00, sizeof f);
    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=m; j>=v[i]; --j) // 逆序进行更新
            f[j]=max(f[j], f[j-v[i]]+w[i]);

    cout<<f[m]<<endl;

    return 0;
}