B - 最少硬币问题

B - 最少硬币问题

Description

设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。 对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。 对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。

Input

输入数据第一行中只有1个整数给出n的值,第2行起每行2个数，分别是T[j]和Coins[j]。最后1行是要找的钱数m。

Output

输出数据只有一个整数，表示计算出的最少硬币数。问题无解时输出-1。

Sample

Input 

3 1 3 2 3 5 3 18

Output 

5

SubmitSolutions

最少硬币问题其实就是多重背包问题，可以这么理解：

第一步：我们现在有面值1,2,5元的硬币各三个，当我们找零金额为0元的时候，显而易见需要的硬币个数为0，即dp[0]=0；

第二步：找零金额为1元时，需要找一个一元即可，因为我们有一元硬币，所以在第一步的基础上加一即可，dp[1]=dp[0]+1=1;

第三步：当i=2时，我们解决的办法是不是可以理解为在找零金额一元的基础上再找给买家一元，即再多找给一个硬币，dp[2]=dp[1]+1=2,但是显然建立在第二步时不是i=2时的最优解，因为我们有两元的硬币，此时的最优解应该建立在第一步上，在第一步的基础上加上一个2元硬币，dp[2]=1;

当我们i=5 的时候情况与i=2类似，需要建立在第一步的基础上加一。

由此来看最少硬币问题似乎是建立在第一步的基本公理上的，但实际情况是第i步的最优解是建立在之前的某一步的最优解上加一得来的，即dp[i]=dp[j]+1;(j<i)

所以用最通俗的话来说就是我们需要凑出 i 元，就在凑出 j 的结果上再加上某一个硬币就行了，具体是哪一个硬币就需要每个都试一次。

dp[i]=dp[j]+1=dp[i-1]+1;||dp[i]=dp[j]+1=dp[i-2]+1;||dp[i]=dp[j]+1=dp[i-5]+1

所有的情况都试出来之后进行比较，取最小的那一种情况就是最优解。

AC代码：

#include<bits/stdc++.h> #define INF 9999 using namespace std; struct Coins {//使用结构体比较方便 int t; int c; } coins[20]; int min(int a,int b) { return a>b?b:a; } int main() { int n,dp[30000],m; cin>>n; for(int i=1; i<=n; i++) { cin>>coins[i].t>>coins[i].c; } cin>>m; for(int i=1; i<=m; i++) {//对数组进行非0，-1的初始化最好不要用memset，有时会乱码，具体为什么还没搞清楚，不建议用memset，本题数据量较小，老老实实用for循环遍历就好 dp[i]=INF; } for(int i=1; i<=n; i++) { for(int j=1; j<=coins[i].c; j++) { for(int k=m; k>=coins[i].t; k--) { dp[k]=min(dp[k],dp[k-coins[i].t]+1); } } } if(dp[m]==INF) cout<<"-1"<<endl; else cout<<dp[m]<<endl; }