Educational DP Contest E - Knapsack 2 (01背包)

https://atcoder.jp/contests/dp/tasks/dp_e

题目大意：

有N个物品，编号为1，2，…，N。对于每个i (1≤i≤N)，物品I的权重为wi，价值为vi。

Taro决定从N件物品中挑选一些，用背包带回家。背包的容量是W，这意味着所带物品的重量之和必须至多为W（<=W）。

找出Taro带回家的物品价值的最大可能总和。

【注意范围】1≤N≤100 ; 1≤W≤10^9 ; 1≤wi≤W ; 1≤vi≤10^3

Sample Input 1  
3 8
3 30
4 50
5 60
Sample Output 1  
90

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
LL n,m;
LL w[N],v[N],f[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(LL i=1;i<=n;i++)
        {
            cin>>w[i]>>v[i];
        }
        for(LL i=1;i<=N;i++)
        {
            f[i]=MAXN;
        }
        for(LL i=1;i<=n;i++)
        {
            //n的最大取值为100，单个价值最大为1000，总和不超过1e5
            for(LL j=1e5;j>=v[i];j--)
            {
                //如果带上了这个物品我们的总数都会更小的话，那就说明有用
                f[j]=min(f[j],f[j-v[i]]+w[i]);
            }
        }
        LL maxn=0;
        for(LL j=1;j<=1e5;j++)
        {
            //在有效值范围内取最大
            if(f[j]<=m) maxn=max(maxn,j);
        }
        cout<<maxn<<endl;
    }
    return 0;
}