hdu 2191悼念512汶川大地震遇难同胞——珍惜现在，感恩生活多重背包

中国加油！四川加油！

#include <iostream> #include <cmath> #include <cstring> using namespace std; int f[101]; //物品组 int n, m; int ans[32001]; int p, h, c; int count, sum; int main() { //freopen("1.txt", "r", stdin); int t; cin >> t; while(t--) { cin >> n >> m; memset(f, 0, sizeof(f)); for(int i = 0; i < m; i++) { cin >> p >> h >> c; count = 1; sum = 0; while(sum < c) { for(int j = n; j >= p * count; j--) f[j] = max(f[j], f[j - p * count] + h * count); sum += count; count *= 2; if(sum + count > c) count = c - sum; } } cout << f[n] << endl; } return 0; }