POJ 1742 Coins 双肩包题解

POJ 1742 Coins 背包题解

本题使用二进制优化也超时了，所以要使用拖线法优化（我yy的名词，呵呵）。

就是多重背包优化。

要点：

1 在可以分解出答案的点记录剩下了多少个当前值了

2 下一个格可以根据上一个格的值判断是否是可行解。

还是看看这里的解说吧：http://www.hankcs.com/program/cpp/poj-1742-coins.html

这个博客说的非常详细了，应该适合初学者；

不过详细过头了，我快速浏览了下，然后就写自己的程序了。

#include <stdio.h>
#include <memory.h>

const int MAX_N = 101;
const int MAX_M = 100001;
int A[MAX_N];
int C[MAX_N];
int tbl[MAX_M];
int n, m;

int bagDP()
{
	memset(tbl, 0, sizeof(int) * (m+1));
	for (int i = 0; i < n; i++)
	{
		if (!C[i] || !A[i]) continue;
		tbl[0] = C[i]+1;
		for (int j = 1; j <= m; j++)
		{
			if (tbl[j] >= 1) tbl[j] = C[i]+1;
			else if (j >= A[i] && tbl[j-A[i]] > 1) tbl[j] = tbl[j-A[i]]-1;
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++) ans += !!tbl[i];//呵呵== if (tbl[i]) ans++;
	return ans;
}

int main()
{
	while (scanf("%d %d", &n, &m) && (n || m))
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &A[i]);
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &C[i]);
		}
		printf("%d\n", bagDP());
	}
	return 0;
}