POJ 1276 Cash Machine 背包題解

典型的多重背包的應用題解。

可以使用二進制優化，也可以使用記錄目前物品的方法解，速度更加快。

const int MAX_CASH = 100001;
const int MAX_N = 11;
int tbl[MAX_CASH], nums[MAX_N], bills[MAX_N], cash, n;

int bag()
{
	if (cash <= 0 || n <= 0) return 0;
	memset(tbl, 0, sizeof(int) * (cash+1));
	for (int i = 0; i < n; i++)
	{
		tbl[0] = nums[i]+1;
		for (int j = 1; j <= cash; j++)
		{
			if (tbl[j]) tbl[j] = tbl[0];
			else if (j >= bills[i] && tbl[j-bills[i]] > 1)
				tbl[j] = tbl[j-bills[i]]-1;
		}
	}
	for (; !tbl[cash]; cash--);
	return cash;
}

int main()
{
	while (~scanf("%d", &cash))
	{
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d %d", &nums[i], &bills[i]);
		}
		printf("%d\n", bag());
	}
	return 0;
}