Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 4257 Accepted Submission(s): 1757
1 #include <cstring> 2 #include <algorithm> 3 #include <cstdio> 4 #include <iostream> 5 using namespace std; 6 int n,m; 7 struct node 8 { 9 int p,q,v; 10 }a[501]; 11 int dp[5002]; 12 bool cmp(node a,node b) 13 { 14 return a.q-a.p<=b.q-b.p; 15 } 16 int main() 17 { 18 int i,j; 19 freopen("in.txt","r",stdin); 20 while(scanf("%d%d",&n,&m)!=EOF) 21 { 22 memset(dp,0,sizeof(dp)); 23 for(i=0;i<n;i++) 24 scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v); 25 sort(a,a+n,cmp); 26 for(i=0;i<n;i++) 27 { 28 for(j=m;j>=a[i].q;j--) 29 dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v); 30 } 31 printf("%d\n",dp[m]); 32 } 33 }
Proud Merchants(POJ 3466 01背包+排序)
原文:http://www.cnblogs.com/a1225234/p/5241668.html