本文出自：http://blog.csdn.net/svitter

原题：http://acm.hdu.edu.cn/showproblem.php?pid=2191

题意：多重背包问题。转换成为01背包解。多重背包转化为01背包的关键在于把件数从整体中孤立出来作为一个新的个体，也就是说不管分类，有多少件就有多少种。

AC代码：

//============================================================================

// Name        : 动态规划.cpp

// Author      :

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

#define max(a,b) a > b ? a : b

struct Rice{

	int pr;

	int val;

};

int f[110];

Rice r[4000];

void ace(){

	//work point

	int t, i , j ,k;

	//num

	int n, m;

	int p, h, c;

	int num;//转换为01背包后的数量

	scanf("%d", &t);

	while(t--){

		memset(f, 0, sizeof(f));

		scanf("%d%d", &n, &m);

        num = 0;

		for(i = 0; i < m; i++){

			scanf("%d%d%d", &p, &h, &c);

			for(j = num; j < num + c; j++){

				r[j].pr = p;

				r[j].val = h;

			}

			num = j;

		}

		//背包最小额

		for(i = 0; i < num; i++){

			for(j = n; j >= r[i].pr; j--){

				f[j] =  max(f[j], f[j - r[i].pr] + r[i].val);

			}

		}

		printf("%d\n", f[n]);

	}

}

int main() {

	ace();

	return 0;

}