The trouble of Xiaoqian HDU - 3591

多重背包 + 完全背包 题目描述：xiaoqian需要买T钱的货物，他有n种不同面值的硬币，每种硬币是有限个。他给收银员钱，收银员找给他钱（如果需要找钱的话），收银员总是给他最少的硬币数目。求xianqian最少需要接触多少硬币（他给收银员的，收银员给他的）。 解题分析：可以分别计算xiaoqian给收银员的钱需要的最少硬币数，和收银员给它的硬币的最少数目。这样就转换成了多重背包和完全背包（收银员硬币数目不限）。因为需要求最小值，初始化时除了0,其他都初始化为无穷大。最后求二者的最小和就是解。

代码如下：

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 20000 + 10; int v[maxn]; int c[maxn]; int dp1[maxn*2];//花费i元钱消耗的最少票子的张数 int dp2[maxn*2]; int n,m; void read() { for(int i = 1; i <= n; i++) { scanf("%d",&v[i]); } for(int i = 1; i <= n; i++) { scanf("%d",&c[i]); } } void compepack(int v) { for(int i = v; i <= 20000; i++) { dp1[i] = min(dp1[i], dp1[i-v] + 1); } } void zeroonepack(int v,int k) { for(int i = 20000; i >= v; i--) { dp1[i] = min(dp1[i],dp1[i-v] + k); } } int main() { int kase = 0; while(scanf("%d %d",&n,&m)==2&&(n||m)) { read(); memset(dp1,0x3f,sizeof(dp1)); dp1[0] = 0; for(int i = 1; i <= n; i++) { if(c[i]*v[i] >= m) { compepack(v[i]); } else { int cnt = c[i]; int k = 1; while(k <= cnt) { zeroonepack(k*v[i],k); cnt -= k; k <<= 1; } if(cnt > 0) zeroonepack(cnt*v[i],cnt); } } memset(dp2,0x3f,sizeof(dp2)); dp2[0] = 0; for(int i = 1; i <= n; i++) { for(int j = v[i]; j <= 20000; j++) { dp2[j] = min(dp2[j],dp2[j-v[i]] + 1); } } int ans = INF; for(int i = 0; i <= 20000; i++) { ans = min(ans,dp1[m+i] + dp2[i]); } if(ans >= INF) printf("Case %d: -1\n",++kase); else printf("Case %d: %d\n",++kase,ans); } return 0; }

注意题目最后一句话，圈定了背包的上限，没读明白的话，这个题不好办。