01背包问题的通俗理解（适合小白）

//算法思想：看了那么多的题解，一个真正让我这个dp小白看明白的也没有（也许是我脑子笨）...
//在其他大佬的题解的基础上，我觉得最重要的一点是明白以下两条语句的作用：
//(如果你跟我一样是dp小白，那就多读几遍下面这段话)
//f[i][j] = f[i-1][j];
//if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
//这两个语句的真正意义：
//意思是我当前的f[i][j]首先要等于不加第i个物品时的最大值f[i-1][j]，但是如果我的第i个物品
//的体积小于总体积j（注意这里是枚举的当前的总体积），说明什么呢？说明我可以把第i个物品放
//进我的背包试一试，但是我如果把第i个物品放进背包，那就必须从里面拿出一些其他的物品。我的
//目的是比较在放进物品i之前和放进物品i之后的两种状态，究竟是哪种状态的得到得值最大（因为
//题目就是求得最大值），拿出其他物品的操作对应代码f[i-1][j-v[i]](这个f[i-1][j-v[i]]的意
//义是在体积为j-v[i]，物品数量为i-1的情况下的最大值)，拿出体积为v[i]的物品之后才能放进
//第i个物品，放进第i个物品对应代码+w[i]，再利用max(f[i][j], f[i-1][j-v[i]]+w[i])就达到
//了判断是否要放第i个物品的目的。
//二维数组版本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=1005;

int f[N][N];
int v[N],w[N];
int m,n;
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>w[i];
    }

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

    // for(int i=0;i<=m;i++){
    //     for(int j=0;j<=n;j++){
    //         cout<<f[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    cout<<f[m][n];

    return 0;
}

//一维数组版本
//与二位版本的道理相同同样需要理解语句：f[j] = max(f[j], f[j - v[i]] + w[i]);
//需要注意的一点就是更新f数组的时候必须是从后往前遍历，为什么必须是从后往前遍历呢？
//因为如果是从前往后遍历，由于我们是不断更新f这个数组的，我们更新的过程中，会把从前的数组
//中的值覆盖掉，从后往前遍历能避免这种情况的发生。

//但是我个人觉得用一维数组虽然代码简短，但是不如二维数组好理解，而且时间复杂度相同，所以
//直接理解二维的那种方法就可以了。
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
   cin>>m>>n;

   for(int i=1;i<=m;i++) cin>>v[i]>>w[i];

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