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;
}
注意题目最后一句话，圈定了背包的上限，没读明白的话，这个题不好办。
