参考别人的思路：http://blog.163.com/zjut_nizhenyang/blog/static/1695700292011212101659204/
hdu 3591 The trouble of Xiaoqian 多重背包+完全背包
题意：货币系统有 N 种不同面值的钱，每种钱的价值分别为 V1,V2,...,VN 一个人要买价值和为 T 的商品，他每种分别相应的带了 C1,C2,...,CN ，然后问你交易完成后所需要经手的钱币最少数目
思路：先对人进行多重背包，然后对售货员进行完全背包
答案其实和以前做的那题 背包超过容量的处理是一样的（uva 10819）
一直情况就是那个人所带的钱刚好凑成了 T ，那么就不需要找钱了，否则就需要找钱，相当于那个人支付了他所能付的超过 T 的钱 M，然后售货员找钱 M-T ，把这两者的经手的钱数加起来就行了
初始化的时候除了 dp[0]=0 之外，其它的都为 inf 表示 i 这个状态是可以由商品组合起来的
否则如果全部初始化为 0 的话，i 只能说是一个上界
#include<iostream>
#include<cstdio>
using namespace std;
const int inf=1000000000;
int V[110],C[110],N,T,dp1[20010],dp2[20010];
int main()
{
int c=1;
while(scanf("%d %d",&N,&T)&&(N||T))
{
//memset(dp1,63,sizeof(dp1));
dp1[0]=0;
for(int i=1;i<=20000;i++)//20000不是2000
{
dp1[i]=inf;
dp2[i]=inf;
}
for(int i=1;i<=N;i++)
{
scanf("%d",&V[i]);
}
for(int i=1;i<=N;i++)
{
scanf("%d",&C[i]);
}
for(int i=1;i<=N;i++)//对xiaoqian进行多重背包
{/*
for(int k=1;C[i];k*=2)
{
if(C[i]<k)
k=C[i];
int S=k*V[i];
for(int j=20000;j>=S;j--)
dp1[j]=min(dp1[j],dp1[j-S]+k);
C[i]-=k;
}
}*/
if(C[i]==0)
continue;
else
{
if(V[i]*C[i]>20000)
for(int j=V[i];j<=20000;j++)//是j++不是i++
{
if(dp1[j]>dp1[j-V[i]]+1)
dp1[j]=dp1[j-V[i]]+1;
}
else
{
int k=1,amount=C[i],temp;
while(k<amount)
{
temp=k*V[i];
for(int j=20000;j>=temp;j--)
if(dp1[j]>dp1[j-temp]+k)
dp1[j]=dp1[j-temp]+k;
amount-=k;
k*=2;
}
/*while(k<amount)*****错了
{
for(int j=k*V[i];j<=20000;i++)
{
if(dp1[j]>dp1[j-k*V[i]]+k)
dp1[j]=dp1[j-k*V[i]]+k;
}
amount-=k;
k*=2;
}*/
for(int j=20000;j>=amount*V[i];j--)
if(dp1[j]>dp1[j-amount*V[i]]+amount)
dp1[j]=dp1[j-amount*V[i]]+amount;
}
}
}//******************************for
//*****对店主进行完全背包******
//memset(dp2,63,sizeof(dp2));
dp2[0]=0;
for(int i=1;i<=N;i++)
{
for(int j=V[i];j<=20000;j++ )
{
if(dp2[j]>dp2[j-V[i]]+1)
dp2[j]=dp2[j-V[i]]+1;
}
}
int ans=inf;
for(int i=T;i<=20000;i++)
if(ans>dp1[i]+dp2[i-T])
ans=dp1[i]+dp2[i-T];
/*for(int i=T;i<=20000;i++)
cout<<dp1[i]+dp2[i-T]<<" *";*/
if(ans==inf)
printf("Case %d: -1\n",c++);
else
printf("Case %d: %d\n",c++,ans);
}
system("pause");
return 0;
}
/*
#include<iostream>
#include<cstdio>
using namespace std;
const int inf=20000;
int V[110],C[110],N,T,dp[20010];
void ZeroOnePack(int cost,int weight)
{
for(int i=;i>=cost;i--)
if(dp[i]>dp[i-cost]+weight)
dp[i]=dp[i-cost]+weight;
}
void CompletePack(int cost,int weight)
{
for(int i=cost;i<=T;i++)
if(dp[i]>dp[i-cost]+weight)
dp[i]=dp[i-cost]+weight;
}
void MutiplePack(int cost,int weight,int amount)
{
if(amount*cost>=T)
{
CompletePack(cost,weight);
return;
}
else
{
int k=1;
while(k<amount)
{
ZeroOnePack(k*cost,k*weight);
amount-=k;
k*=2;
}
ZeroOnePack(amount*cost,amount*weight);
}
}
int main()
{
int c=1;
while(scanf("%d %d",&N,&T)&&(N||T))
{
dp[0]=0;
for(int i=1;i<=10000;i++)
dp[i]=inf;
for(int i=1;i<=N;i++)
{
scanf("%d",&V[i]);
}
for(int i=1;i<=N;i++)
{
scanf("%d",&C[i]);
}
for(int i=1;i<=N;i++)
{
if(c[i]==0)
continue;
else if(C[i]==1)
ZeroOnePack(V[i],1);
else
MutiplePack(V[i],1,C[i]);
}
if(dp[T]>=20000)
printf("Case %d: -1\n",c++);
else
printf("Case %d: %d\n",c++,dp[T]);
}
system("pause");
return 0;
}
*/