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