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;
}