#include <iostream>#include <string.h>#define N 50002#define M 2002using namespace std; //测试OJ：nyoj 311 /*    背包不允许剩余，与允许剩余相比，只需将d[i]初始为负无穷大，d[0]=0    d[i]: 用去i容量时的最大价值 */ int d[N];struct Node {    int pri;    int vol;}c[M]; int main(){    freopen("D:/Documents/work/in.txt", "r", stdin);    int t, i, j, m, v;    cin>>t;    while(t--)    {        cin>>m>>v;        memset(d, -1000000, sizeof(d));        d[0]=0;        for(i=0; i<m; i++)            cin>>c[i].vol>>c[i].pri;        for(i=0; i<m; i++){            for(j=c[i].vol; j<=v; j++){                if(j>=c[i].vol)                    d[j]=max(d[j], d[j-c[i].vol]+c[i].pri);                    //d[j]表示装当前的货，d[j-c[i].vol]+c[i].pri表示替换成当前的货物             }        }        if(d[v]<0) cout<<"NO"<<endl;        else cout<<d[v]<<endl;    }    return 0;}

#include <iostream>#include <string.h>using namespace std;#define N 20000int d[N]={0};int w[102];int v[102];/*    背包问题：大容量背包问题    测试oj：nyoj 860    由于背包容量太大，无法开出内存，将问题转化，价值和容量互换    一共w容量装价值v的货物，使v最大问题 转化为     一共有v价值的货物用w容量来装，使w容量内v最大        遗留问题：d初始值大于这个或小于这个都可能无法过oj测试用例 */int main(){//    freopen("D:/Documents/work/in.txt","r",stdin);    int n, i, j, p, c;//c 可容纳重量     while(cin>>n>>c)    {        int sum=0;//总价值         for(i=0; i<n; i++){            cin>>w[i]>>v[i];            sum+=v[i];        }        memset(d, 1000000, sizeof(d));        d[0]=0;        for(i=0; i<n; i++){            for(j=sum; j>=v[i]; j--)                d[j]=min(d[j], d[j-v[i]]+w[i]);        }        int result=0;// 可容纳重量内的最大价值         for(i=sum; i>=0; i--)            if(d[i]<=c){                 result=i;                 break;            }        cout<<result<<endl;     }    return 0;}