ProudMerchants(01背包)

 1 #include
 2 #include<string.h>
 3 #include
 4 #define MAX(x,y)(x>y?x:y)
 5 const int MAXN=5010;
 6 const int MAXM=510;
 7 struct Node{
 8     int p,q,v;
 9 };
10 int cmp(const void *a,const void *b){
11     if((*(Node *)a).q-(*(Node *)a).p<(*(Node *)b).q-(*(Node *)b).p)return -1;
12     else return 1;
13 }
14 Node dt[MAXM];
15 int bag[MAXN];
16 int main(){
17     int N,M;
18     while(~scanf("%d%d",&N,&M)){
19         memset(bag,0,sizeof(bag));
20         for(int i=0;i"%d%d%d",&dt[i].p,&dt[i].q,&dt[i].v);
21         qsort(dt,N,sizeof(dt[0]),cmp);
22         for(int i=0;i)
23             for(int j=M;j>=dt[i].q;j--){//
24                     if(j>=dt[i].p){//
25                         bag[j]=MAX(bag[j],bag[j-dt[i].p]+dt[i].v);
26                     }
27             }
28             printf("%d\n",bag[M]);
29     }
30     return 0;
31 }