题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2191
题目大意：
中文题
思路：
裸的多重背包
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int INF = 0x3f3f3f3f; 6 const int maxn = 200 + 10; 7 int T, n, m, cases; 8 int cost[maxn], weight[maxn], amount[maxn], dp[maxn]; 9 void zeroone(int cost, int weight) 10 { 11 for(int i = n; i >= cost; i--) 12 dp[i] = max(dp[i], dp[i - cost] + weight); 13 } 14 void complete(int cost, int weight) 15 { 16 for(int i = cost; i <= n; i++) 17 dp[i] = max(dp[i], dp[i - cost] + weight); 18 } 19 void solve(int cost, int weight, int amount) 20 { 21 if(cost * amount >= n) 22 complete(cost, weight); 23 else 24 { 25 int k = 1;//二进制优化 26 while(k <= amount) 27 { 28 zeroone(k * cost, k * weight); 29 amount -= k; 30 k *= 2; 31 } 32 zeroone(amount * cost, amount * weight); 33 } 34 } 35 int main() 36 { 37 cin >> T; 38 while(T--) 39 { 40 cin >> n >> m; 41 memset(dp, 0, sizeof(dp)); 42 for(int i = 0; i < m; i++) 43 cin >> cost[i] >> weight[i] >> amount[i]; 44 for(int i = 0; i < m; i++) 45 solve(cost[i], weight[i], amount[i]); 46 cout<<dp[n]<<endl; 47 } 48 return 0; 49 }