知识点：DP之01背包

(原始二维写法) $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int N,V;
int w[maxn],v[maxn],f[maxn][maxn];
//w[i]表示第i个物品的价值
//v[i]表示第i个物品的体积
//f[i][j]表示在前i件物品中选择总体积不超过j的物品的最大价值
int main(){
    cin>>N>>V;
    for(int i=1;i<=N;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=V;j++){
            f[i][j]=f[i-1][j];//先假设背包装不下第i件物品，只能在前i-1件物品中选
            if(j>=v[i]){//如果背包能装下第i件物品
                //则在选第i件物品与不选第i件物品之间选一个最价值最大的
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            }
        }
    }
    cout<<f[N][V]<<endl;//在前N件物品中选总体积不超过V的物品的最大价值
    return 0;
}

(优化后一维写法) $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int N,V;
int w[maxn],v[maxn],f[maxn];
//w[i]表示第i个物品的价值
//v[i]表示第i个物品的体积
//f[j]表示在前某些件物品中选择总体积不超过j的物品的最大价值
int main(){
    cin>>N>>V;
    for(int i=1;i<=N;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=N;i++){
        //装不下第i件物品，则f[j]（本层的）=f[j]（上一层的）
        for(int j=V;j>=v[i];j--){//背包能装下第i件物品
            //则在选第i件物品与不选第i件物品之间选一个最价值最大的选法
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[V]<<endl;//在前N件物品中选总体积不超过V的物品的最大价值
    return 0;
}