POJ 3260 The Fewest Coins / 混合背包

给钱+找钱花的硬币最少

给钱多重背包 找钱01背包 然后背包上限不知道 据说是抽屉原理 我还没学过 然后有空在学

多重背包我用2进制优化

01背包 以为是要在多重背包的基础上减 背包的价值是负数所以 我是倒过来处理的

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 130;
const int maxm = 25010;
int dp[maxm];
int dp2[maxm];
int a[maxn];
int b[maxn];
int n, t;
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++)
		scanf("%d", &b[i]);
	for(int i = 1; i <= maxm; i++)
		dp[i] = 999999999;
	dp[0] = 0;
	for(int i = 1; i <= n; i++)
	{
		int k = 1;
		while(k <= b[i])
		{
			for(int j = maxm; j >= k*a[i]; j--)
				dp[j] = min(dp[j], dp[j-k*a[i]]+k);
			b[i] -= k;
			k *= 2;
		}
		if(b[i] > 0)
		{
			k = b[i];
			for(int j = maxm; j >= k*a[i]; j--)
				dp[j] = min(dp[j], dp[j-k*a[i]]+k);		
		}
		
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = maxm-a[i]; j >= 0; j--)
			dp[j] = min(dp[j], dp[j+a[i]]+1);
	}
	if(dp[m] == 999999999)
		dp[m] = -1;
	printf("%d\n", dp[m]);
	return 0;
}

POJ 3260 The Fewest Coins / 混合背包,布布扣,bubuko.com

POJ 3260 The Fewest Coins / 混合背包

原文：http://blog.csdn.net/u011686226/article/details/22395207