完全背包
1 #include<iostream> 2 #include<memory.h> 3 #include<cmath> 4 using namespace std; 5 #define maxn 505 //刚开始不小心打成105了、、、只有75，改成505，就100了 6 #define maxm 100005 7 int need[maxn],value[maxm]; 8 int dp[maxm]; 9 int main() 10 { 11 int n,m; 12 while(cin>>n>>m) 13 { 14 for(int i = 1; i <= n; i++) 15 cin>>need[i]>>value[i]; 16 memset(dp,0,sizeof(dp)); 17 for(int i = 1; i <= n; i++) 18 for(int j = need[i]; j <= m; j++) 19 dp[j] = max(dp[j],dp[j - need[i]] + value[i]); 20 cout<<dp[m]<<endl; 21 } 22 return 0; 23 }