Hrbust1814 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1814
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 struct s 6 { 7 int c,val; 8 }p[105]; 9 using namespace std; 10 int dp[1005]; 11 int main() 12 { 13 int sum,v; 14 while(cin>>sum>>v){ 15 memset(dp,0,sizeof(dp)); 16 for(int i=0;i<sum;i++){ 17 cin>>p[i].c>>p[i].val; 18 } 19 for(int i=0;i<sum;i++){ 20 for(int j=v;j>=p[i].c;j--){ 21 dp[j]=max(dp[j],dp[j-p[i].c]+p[i].val); 22 23 } 24 } 25 cout<<dp[v]<<endl;} 26 27 28 }