背包问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define int long long 
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define For(i, x) for (int i = 0; i < x; i++)
#define For1(i, x) for (int i = 1; i <= x; i++)
int n,V;
int v[N],w[N];
int dp[N];
signed main(){
    FAST
    //二维
//  cin>>n>>V;
//  For1(i,n)cin>>v[i]>>w[i];
//  for(int i=1;i<=n;i++){//遍历物品
//      for(int j=1;j<=V;j++){//遍历容量
//          if(j>=v[i]){
//              dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
//          }
//          else dp[i][j]=dp[i-1][j];
//      }
//  }
//  cout<<dp[n][V];

    //一维优化
    cin>>n>>V;
    For1(i,n)cin>>v[i]>>w[i];//可以边输入边遍历

    for(int i=1;i<=n;i++){//遍历物品
        for(int j=V;j>=v[i];j--){//倒序遍历容量 不会出现容量不够的情况
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V];




    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define int long long 
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define For(i, x) for (int i = 0; i < x; i++)
#define For1(i, x) for (int i = 1; i <= x; i++)
int n,V;
int v[N],w[N];
int dp[N];
signed main(){
    FAST
    cin>>n>>V;
    For1(i,n)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=V;j++){//顺序遍历 因为后面要用到前面的数据 相当于是叠加上来的
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V];

    return 0;
}