POJ 1742 Coins（多重背包） DP

参考：http://www.hankcs.com/program/cpp/poj-1742-coins.html

题意：给你n种面值的硬币，面值为a1...an，数量分别为c1...cn，求问，在这些硬币的组合下，能够多少种面值，该面值不超过m

思路：设d[i][j]——前i种硬币，凑成总值j时，第i种硬币所剩余的个数。

　　　默认d[i][j] = -1，代表无法凑成总值j

　　　转移方程为，若d[i-1][j]≥0，代表前i-1种已能够凑成j，那么就不必花费第i种硬币，所以d[i][j] = c[i]

　　　否则就看d[i][j-a[i]]的值，显然如果j < a[i]，那么d[i][j] = -1，否则d[i][j-a[i]] ≤ 0，代表此刻第i种硬币已使用完了，所以自然d[i][j] = -1;

　　　否则，d[i][j] = d[i][j-a[i]]-1;

　　　可以看到d[i][]的值只与d[i-1][]和d[i][]有关，所以我们可以采用一维数组的形式，从而能够节省内存空间。

AC代码：

#include <cstdio>

#include <cstring>

using namespace std;

const int M = 100005;

const int N = 105;

int d[M];

int n,a[N],c[N],m;

void solve()

{

	memset(d, -1, sizeof(d));

	d[0] = 0;

	for(int i = 0; i < n; i++)

	{

		for(int j = 0; j <= m; j++)

		{

			if(d[j] >= 0) d[j] = c[i];

			else if(j < a[i] || d[j-a[i]]<= 0)

				d[j] = -1;

			else d[j] = d[j-a[i]]-1;

		}

	}

	int ans = 0;

	for(int i = 1; i <= m; i++)

		if(d[i]>=0) ans++;

	printf("%d\n", ans);

}

int main()

{

	//freopen("in.txt", "r", stdin);

	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);

		solve();

	}

	return 0;

}