题目描述

Bob 是个聪明的小孩，他在小学的时候就已经掌握了 01 背包的使用方法。所谓 01 背包问题，就是从 n 个物品中（每个物品有 w[i]的重量和 v[i]的价值）选出若干个，每个物品可以选或者不选，使得在总重量不超过 m 的情况下，总价值最大。

有一天，Bob 买到了一个背包，这个背包能够承受重量也是 m。不一样的是，这个背包有一个特别的性质：如果背包还没满的话，放入下一件物品之后，背包内的重量可以超过 m。例如有 3 件物品，物品 1 的重量和价值分别为 3,3，物品 2 的为 2,1，物品 3 的为 3,3。假如背包的承受重量 m 为 6：

第一种情况下：先放入物品 1，3；则此时背包已满，不能放入物品 2，故最后的总价值为 6。

第二种情况下：先放入物品 1，2；此时背包中的重量为 5，还没有满，故可以继续放入物品 3。此时虽然背包的重量为 8，但是符合我们的条件，因此总价值为 7。

输入

输入一共有 3 行，第一行依次为 n（物品数量）,m（背包重量）。其中 n≤2000，m≤2000。

第二行包含 n 个整数 w[i]（1≤Wi≤2000）。

第三行包含 n 个整数 v[i]（1≤Ci≤10^6）。

输出

输出共一行，为使用这个神奇背包能背的最大价值总和。

样例输入

【样例1】

3 6

3 3 2

3 3 1

【样例2】

3 5

3 3 2

3 3 10

样例输出

【样例1】

7

【样例2】

13

提示

对 30%的数据，n<20。

对 60%的数据，n<100。

对 100%的数据，n≤2000。

取一个v+maxv体积的背包即可，简单题

#include
using namespace std;
#define int long long
const int N=4010;
int dp[N];
int f[N];
int n,m;
struct node
{int w,v;
} Node[N];
bool cmp(node a,node b)
{return a.w>n>>m;int maxf=0;for(int i=1; i<=n; i++){cin>>Node[i].w;maxf=max(maxf,Node[i].w);}for(int i=1; i<=n; i++){cin>>Node[i].v;}sort(Node+1,Node+1+n,cmp);//    cout<=Node[i].w; j--){if(dp[j]=0; j--){mmax=max(mmax,dp[j]);}cout<