POJ3260 – The Fewest Coins(可以找零的混合背包+鸽巢定理)

【题目链接】 POJ3260

【题意】有N种货币，面值分别为v1~vn;John对于这些面值的货币分别有c1~cn个，现在John想去商店买价格为v的商品，怎样让John付款的货币数加上商店找零的货币数量最少，商店对于每种货币有无数个。

【分析】复习了一下背包问题，又学到了点，对应John的付款用多重背包+完全背包就能做了，而对于找零用一次完全背包就好了，关键是求出最高能达到多少货币值的上线：这个还没理解，暂时记记住：

John的付款数最多为maxv*maxv+m，也就是24400元。同理，shopkeeper找钱最多的数目为maxv*maxv.证明如下：

如果John的付款数大于了maxv*maxv+t，即付硬币的数目大于了maxv，根据鸽笼原理，至少有两个的和对maxv取模的值相等，也就是说，这部分硬币能够用更少的maxv来代替。

【AC CODE】47ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100+10, MAXM = 120*120+10000+10;
/*POJ3260;付款最多不超过maxv*maxv+t(maxv是货币种类的最大值，t是购买物品的值)*/
int v[MAXN],c[MAXN],dp[MAXM];

int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int n,t;
	while(~scanf("%d %d%*c", &n, &t))
	{
		int mv = -1;
		rep(i,0,n)
		{
			scanf("%d%*c", &v[i]);
			if(mv < v[i]) mv = v[i];
		}
		int m = mv*mv+t+1;//鸽巢定理
		rep(i,0,n) scanf("%d%*c", &c[i]);
		/*付款的混合背包*/
		clc(dp,0x3f);
		dp[0] = 0;
		rep(i,0,n)
		{
			if(c[i]*v[i] >= m)
				repe(j,v[i],m) dp[j] = min(dp[j],dp[j-v[i]]+1);
			else
			{
				for(int j = 1; j <= c[i]; c[i] -= j, j<<=1)
				{
					int w = j*v[i];
					per(k,m,w) dp[k] = min(dp[k],dp[k-w]+j);
				}
				if(c[i] > 0)
				{
					int w = c[i]*v[i];
					per(k,m,w) dp[k] = min(dp[k],dp[k-w]+c[i]);
				}
			}
		}
		/*倒过来的完全背包，用于找零;
		也可以用另外一个数组r[]记录正常的完全背包，最后扫一遍min{dp[i+m]+r[i]}*/
		rep(i,0,n)
		{
			per(j,m-v[i],0)
				dp[j] = min(dp[j], dp[j+v[i]]+1);
		}
		if(INF != dp[t]) printf("%d\n", dp[t]);
		else puts("-1");
	}
	return 0;
}