背包问题 - AcWing 2. 01背包问题（C++）- 简单

题目链接：https://www.acwing.com/problem/content/description/2/
题目如下：

二维数组dp：

#include 
#include 
#include 
using namespace std;

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

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++){//对n个物品进行决策
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];//不选第i个物品
            if(j>=v[i]){//当容量j<当前物品的体积v[i],则不能选第i个物品
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);//选第i个物品
            }
        }
    }
    
    int res=0;
    for(int i=0;i<=m;i++) res=max(res,f[n][i]);//选出物品决策的最大价值
    
    cout< 
优化为一维dp：
 
#include 
#include 
#include 
using namespace std;

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

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++){//对n个物品进行决策
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);//选第i个物品
        }
    }
    
    cout<