01背包Bone Collector

今天复习背包，之前集训讲过，现在又忘了，昨天杭电校赛刚好有一题背包，居然不会做了，好尴尬，重新复习一下。

https://vjudge.net/contest/150953#problem/A

可以说是最基础的01背包了

#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

const int maxn=600,N=1005;

int main()
{
    int t,n,W;
    ll v[N],w[N],dp[N];
    cin>>t;
    while(t--){
        memset(dp,0,sizeof(dp));
        cin>>n>>W;
        for(int i=0;i<n;i++)cin>>v[i];
        for(int i=0;i<n;i++)cin>>w[i];
        for(int i=0;i<n;i++)
            for(int j=W;j>=w[i];j--)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
       cout<<dp[W]<<endl;
    }
    return 0;
}

最重要的就是状态转移方程了dp[j]=max(dp[j],dp[j-w[i]]+v[i]);