【一本通OJ 1601：【例 5】Banknotes】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905471.html

题目链接

题目

原题来自：POI 2005

Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 $n$ 种面值的硬币，面值分别为 $b_1, b_2,\cdots , b_n$ 。但是每种硬币有数量限制，现在我们想要凑出面值 $k$，求最少要用多少个硬币。

思路

首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。

同时，我们也可以把每种面值的货币拆成 $c_i$ 个，用01背包求解。时间复杂度为 $O(nm^2)$。

这时我们可以考虑每种面值。设 $t=log_2c_i$，对于 $c_i$ 以内的任何一个数，我们都可以用 $2^0, 2^1,\cdots,2^t$ 凑出，所以我们并不需要把每种面值的硬币拆成 $c_i$ 份，拆成 $log_2c_i$ 份即可。

时间复杂度 $O(nm\log m)$。

总结

这是一道经典的多重背包优化题目。

对于多重背包来说，数量的个数限制往往可以用二进制的方法组合表示。

如果一道多重背包的题能拆成01背包，那么它必然可以用二进制的方法进行优化，这是一种常见题型。

Code

{33, 34, 39}

// Problem: 1601：【例 5】Banknotes
// Contest: SSOIER
// URL: http://ybt.ssoier.cn:8088/problem_show.php?pid=1601
// Memory Limit: 524 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define mo
#define N 210
#define M 200010
int n, m, i, j, k; 
int b[N], c[N], v[M], w[M], dp[M]; 

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	memset(dp, 0x3f, sizeof(dp));
	n=read(); dp[0]=0; 
	for(i=1; i<=n; ++i) b[i]=read(); 
	for(i=1; i<=n; ++i) c[i]=read(); 
	for(i=1; i<=n; ++i)
	{
		k=log2(c[i]); 
		if(c[i]-k) v[++m]=(c[i]-k)*b[i], w[m]=c[i]-k; 
		for(j=1; k; k--, j*=2) v[++m]=j*b[i], w[m]=j; 
	}
	n=m; m=read(); 
	for(i=1; i<=n; ++i)
		for(j=m; j>=v[i]; --j)	 
			dp[j]=min(dp[j], dp[j-v[i]]+w[i]); 
	printf("%lld", dp[m]); 
	return 0;
}