http://acm.hdu.edu.cn/showproblem.php?pid=1248
完全背包....
View Code
1 #include <iostream> 2 #define maxn 10005 3 using namespace std; 4 int ans[maxn],v[3]; 5 int main() 6 { 7 int n, t, i, j; 8 v[0] = 150; 9 v[1] = 200; 10 v[2] = 350; 11 cin >> t; 12 while(t--) 13 { 14 cin >> n; 15 for(i = 0; i <= n; i++) ans[i] = 0; 16 for(i = 0; i < 3; i++) 17 for(j = 0; j <=n; j++) 18 { 19 if(j >= v[i] && ans[j-v[i]]+v[i] > ans[j]) 20 ans[j] = ans[j-v[i]]+v[i]; 21 } 22 cout << n-ans[n] << endl; 23 } 24 return 0; 25 }