#include <stdio.h>
#define mun(a, b) ((a) > (b) ? (a) : (b))
int result[100005];
int cash, n;

void ZeroOnePack(int cost)		//01背包问题的一维数组优化, 逆序求解
{
	int i;
	for(i = cash; i >= cost; i--)
		result[i] = mun(result[i], result[i - cost] + cost);
}

void CompletePack(int cost)		//完全背包问题，正序求解
{
	int i;
	for(i = cost; i <= cash; i++)
		result[i] = mun(result[i], result[i - cost] + cost);
}

void MultiPack(int cost, int amount)		//多重背包问题转换成01背包问题
{
	if(cost * amount >= cash)		//单一物件超出最大值则转换成完全背包
	{
		CompletePack(cost);
		return;
	}
	int k = 1;
	while(k < amount)
	{
		ZeroOnePack(cost*k);
		amount -= k;
		k *= 2;
	}
	ZeroOnePack(cost*amount);
}

int main()
{
	int i;
	int n1[12], dk[12];
	while(scanf("%d%d", &cash, &n) != EOF)
	{
		for(i = 1; i <= n; i++)
			scanf("%d%d", &n1[i], &dk[i]);
		if(n == 0 || cash == 0)
		{
			cash = 0;
			printf("%d\n", cash);
			continue;
		}
		for(i = 0; i <= n; i++)		//初始化
			result[i] = 0;
		for(i = 1; i <= n; i++)
			MultiPack(dk[i], n1[i]);
		printf("%d\n", result[cash]);
	}
	return 0;
}

• Re:我用多重背包写的，提交几次都是WA，找不出哪错了，求指教！~ (26) ouwery 2012-03-28 21:22:43
• Re:我用多重背包写的，提交几次都是WA，找不出哪错了，求指教！~ (1202) clooszhao 2013-01-24 12:12:17
• Re:我用多重背包写的，提交几次都是WA，找不出哪错了，求指教！~ (10) illuminator 2013-03-24 13:26:14