Description
Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is.
FJ wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change).
Input
Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)
Line 3: N space-separated integers, respectively C1, C2, ..., CN
Output
Sample Input
3 70
5 25 50
5 2 1
Sample Output
3
Hint
解法：支付时硬币数量有限制，为多重背包问题，通过二进制方法转化为01背包求解。找零时，硬币数量无限制，为完全背包问题。对两问题分别求解，然后找出差额为T时，两者和的最小值即为所示。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; #define met(a,b) (memset(a,b,sizeof(a)))
#define N 20000
#define INF 0x3f3f3f3f int V[], C[];
int v[N], c[N], dp[N];
int n, T, sum, k, Update; ///Update为更新的范围， 价值T最大为10000，而V[i]最大为120， 因此Update为10200便可以 void Init() ///将多重背包利用倍增法，转化为01背包
{ ///并解决一些初始化的问题
int i, j; k=;
for(i=; i<=n; i++)
{
for(j=; j<=C[i]; j*=)
{
v[k] = V[i]*j;
c[k++] = j;
C[i] -= j;
}
if(C[i])
{
v[k] = V[i]*C[i];
c[k++] = C[i];
C[i] = ;
}
}
k--; for(i=; i<=Update; i++)
dp[i] = INF;
} void First()
{
int i, j; dp[] = ;
for(i=; i<=k; i++)
{
for(j=Update; j>=v[i]; j--)
dp[j] = min(dp[j], dp[j-v[i]]+c[i]);
}
} int Secound()
{
int i, j; for(i=; i<=n; i++)
{
for(j=Update-V[i]; j>=; j--)
{///看好哦， 这里是加号，也就是从后面更新过来的， 于是第二重循环要逆着来
dp[j] = min(dp[j], dp[j+V[i]]+);
}
} return dp[T];
} int main()
{
while(scanf("%d%d", &n, &T)!=EOF)
{
int i;
sum=;
for(i=; i<=n; i++)
scanf("%d", &V[i]);
for(i=; i<=n; i++)
{
scanf("%d", &C[i]);
sum += V[i]*C[i];
}
Update=; Init(); ///初始化
First();///01背包
int ans = Secound(); ///完全背包 if(T>sum) printf("-1\n");
else
{
if(ans==INF) ///如果ans==INF说明并没有更新到dp[T]，不能兑换到
printf("-1\n");
else
printf("%d\n", dp[T]);
} }
return ;
}