学步园

题目大意：该题是中文的，读者可以直接去看原题。

题目分析：在sampleinput中，我们可以看到以下内容

Sample Input
1
8 2
2 100 4
4 100 2

1  ------测试用例的个数，用t表示

8  -------在这里理解为背包容量，用V表示

 2  ---------物品种类数，用n表示

 2  ----------物品的价格，这时在这种模型中理解为物品的体积，用c[i]表示。因为你的总钱数作为了背包容量。

100 ---------物品的体积。这里理解为物品的价值。用w[i]表示

 4   -----------物品的数量。用amount[i]表示。

只要理解了01背包，完全背包和多重背包，这一道题数这时比较简单的。。。。

代码如下：

/*
 * 2191.c
 *
 *  Created on: 2013年7月30日
 *      Author: 黄东东 
 *      章泽天是我的女神。。。。。。。。。
 */


#include <stdio.h>
#include <string.h>
int n,V,c[105],w[105],amount[105],f[106];

#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a>b)?(b):(a))
void ZeroOnePack(int cost , int weight){
	int v;
	for( v = V ; v >= cost ; --v){

		f[v] = max(f[v],f[v - cost] +weight);
	}
}

void CompletePack(int cost ,int weight){
	int v;
	for(v = cost ; v<= V ; ++v){
		f[v] = max(f[v],f[v-cost]+ weight);
	}
}

void MultiplePack(int cost ,int weight , int amount){

	if(cost*amount > V){
		CompletePack(cost,weight);
	}

	int k = 1;

	while( k < amount){

		ZeroOnePack(k*cost,k*weight);

		amount -= k;

		k<<=1;
	}
	ZeroOnePack(amount*cost,amount*weight);

}
int main(){


	int t ;

	scanf("%d",&t);
	while( t-- ){
		scanf("%d%d",&V,&n);
		int i ;
		for(i = 0 ; i < n ; ++i){
			scanf("%d%d%d",&c[i],&w[i],&amount[i]);
		}

		memset(f,0,sizeof(f));
		for(i = 0 ; i < n ;++i){
			MultiplePack(c[i],w[i],amount[i]);
		}


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

	}
	return 0;
}