【题意】：已知整个交易系统有N
(1 ≤ N ≤ 100)种不同的货币，分别价值V1,V2,V3.......VN(1 ≤ Vi ≤ 120)，FJ分别有C1,C2,C3.....CN(0
≤ Ci ≤10,000)张相应价值货币。FJ只能用仅有的货币去买价值T(1 ≤T≤10,000)分的东西，而老板有无数的货币可以找给他。求FJ给老板的货币数+老板找给FJ的货币数的最小值。
Input
* Line 1: Two space-separated integers: N and T.
* Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1...VN).
* Line 3: N space-separated integers, respectively C1, C2, ..., CN
Output
* Line 1: A line containing a single integer, the minimum number of coins involved in a payment and
change-making. If it is impossible for Farmer John to pay and receive exact change, output -1.Sample Input
3 70
5 25 50
5 2 1
Sample Output
3
【分析】：将问题拆分为两部分：(多重背包+完全背包）FJ支付的货币数实是多重背包问题，而老板找给FJ的货币数可以转化为完全背包问题。
思路一：FJ最多可以给老板（N+他所拥有的货币最大面值），用t[i]保存在此区间FJ支付给老板的钱数为i时所需的最小货币数。对于[N,N+Max]区间，用l[j]表示老板找给FJ的钱数为j时的最小货币数（其中i-j=N），最终求出所有t[i]+l[j]的最小值，即为题目所求。
<span style="font-size:14px;">#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int v[110],c[110],t[24400],l[24400];
int T=0,N=0;
int Max;
const int inf =10000000;
void ZeroOnePack(int vi,int k)
{
for(int i=N+Max;i>=vi;i--)
t[i]=min(t[i],t[i-vi]+k);
}
void CompletePack(int vi,int* t,int n)
{
for(int i=vi;i<=n;i++)
t[i]=min(t[i],t[i-vi]+1);
}
void MultiplePack(int vi,int ci)
{
if(vi*ci>N+Max)
CompletePack(vi,t,N+Max);
int k=1;
while(k<ci)
{
ZeroOnePack(k*vi,k);
ci=ci-k;
k=2*k;
}
ZeroOnePack(ci*vi,ci);
}
int main (void)
{
while(~scanf("%d%d",&T,&N))
{
int Min=inf;
Max=0;
for(int i=1;i<24400i++) t[i]=inf;
t[0]=0;
for(int i=0;i<T;i++)
{
scanf("%d",&v[i]);
if(Max<v[i]) Max=v[i];
}
Max=Max*Max;//保证背包足够大
for(int i=0;i<T;i++) scanf("%d",&c[i]);
for(int i=0;i<T;i++) MultiplePack(v[i],c[i]);
for(int i=N;i<=N+Max;i++)
{
if(t[i]!=inf)
{
for(int i=0;i<24400;i++) l[i]=inf;
l[0]=0;
for(int j=0;j<T;j++)
CompletePack(v[j],l,i-N);
Min=min(Min,t[i]+l[i-N]);
}
}
if( Min==inf) Min=-1;
printf("%d\n",Min);
}
} </span>
【Spotted】
1.最初不知道应该开多大的数组保存货币数，在别人的博客中找到以下内容：
最重要的是上界的处理。可以注意到，上界为maxw*maxw+m（maxw最大面额的纸币），也就是24400元。（网上的证明）证明如下：
如果买家的付款数大于了maxw*maxw+m，即付硬币的数目大于了maxw，根据鸽笼原理，至少有两个的和对maxw取模的值相等，也就是说，这部分硬币能够用更少的maxw来代替。证毕。
【【离散不是白学的呀呵呵！
2.memset和fill相关。。。。在下一篇博客中。。。。
思路二：使用同一个数组【想了好久都感觉无解，看了别人的代码才顿悟。。。。窒息。。。。】
改一下main函数，代码如下：
<span style="font-family:Microsoft YaHei;font-size:14px;">int main (void)
{
while(~scanf("%d%d",&T,&N))
{
int Min=inf;
Max=0;
for(int i=1;i<24400;i++) t[i]=inf;
t[0]=0;
for(int i=0;i<T;i++)
{
scanf("%d",&v[i]);
if(Max<v[i]) Max=v[i];
}
Max=Max*Max;//保证背包足够大 for(int i=0;i<T;i++) scanf("%d",&c[i]);
for(int i=0;i<T;i++) MultiplePack(v[i],c[i]);
for(int i=0;i<T;i++)
{
for(int k= N+Max-v[i]; k>=N; k--)
t[k]=min(t[k],t[k+v[i]]+1);
//由于是老板还给FJ的钱，且是完全背包问题，所以正负号相反，且逆序进行循环
}
if( t[N]==inf) t[N]=-1;;
printf("%d\n",t[N]);
}
}</span>