货币兑换问题 外汇获利的计算方法有

问题描述

考虑下面的货币兑付问题：在面值为 ( v 1 , v 2 , ⋯   , v n ) left(v_1,v_2,cdots,v_n ight) (v1​,v2​,⋯,vn​)的n种货币中，需要支付 y y y值的货币，应如何支付才能使货币支付的张数最少，即满足： ∑ i = 1 n x i v i = y sum_{i=1}^{n}{x_iv_i=y} ∑i=1n​xi​vi​=y，且 ∑ i = 1 n x i sum_{i=1}^{n}x_i ∑i=1n​xi​最小。

输入

（1）货币种类的个数； （2）从小到大输入货币的价值（其中第一个必须为1）； （3）要兑换的钱的价值（整数）。

输出

兑换的货币个数的最小值

测试用例 输入（Input）61 2 5 10 20 5046输出（Output）兑换的最小货币个数是4 解题思路

本题使用动态规划策略进行算法设计。

1.划分子问题

原问题：使用货币 ( v 1 , v 2 , ⋯   , v n ) (v_1,v_2,cdots ,v_n) (v1​,v2​,⋯,vn​)凑出总金额为 m m m的需要的钱币最少数量

int exchange(n,[v1,v2,...,vn],m);

子问题：使用货币 ( v 1 , v 2 , ⋯   , v j ) , j ≤ n (v_1,v_2,cdots ,v_j),j leq n (v1​,v2​,⋯,vj​),j≤n凑出总金额为 i ( i ≤ m ) i(i leq m) i(i≤m)的需要的钱币最少数量

int exchange(j,[v1,v2,...,vj],i);

第1阶段，j=1，考虑钱币面值的所有可能取值为 ( v 1 , ) (v_1,) (v1​,)，凑出总金额为m需要的钱币数量。 第2阶段，j=2，考虑钱币面值的所有可能取值为 ( v 1 , v 2 , ) (v_1,v_2,) (v1​,v2​,)，凑出总金额为m需要的钱币数量。 第j阶段，j=j，考虑钱币面值的所有可能取值为 ( v 1 , v 2 , ⋯   , v j , ) (v_1,v_2,cdots,v_j,) (v1​,v2​,⋯,vj​,),凑出总金额为m需要的最少钱币数。 … 第n阶段，j=n，考虑钱币面值的所有可能取值为 ( v 1 , v 2 , ⋯   , v j , ⋯   , v n ) (v_1,v_2,cdots,v_j,cdots ,v_n) (v1​,v2​,⋯,vj​,⋯,vn​),凑出总金额为m需要的最少钱币数。

2.找递推关系（书上的说法叫动态规划函数） 决定第 j j j个序列 ( v 1 , v 2 , ⋯   , v j ) (v_1,v_2,cdots, v_j) (v1​,v2​,⋯,vj​)的解，是在第 j − 1 j-1 j−1个序列 ( v 1 , v 2 , ⋯   , v j − 1 ) (v_1,v_2,cdots,v_{j-1}) (v1​,v2​,⋯,vj−1​)已经完成的基础上，有三种情况：

第 j j j个面值的货币 v j v_j vj​=需要支付的金额 i i i，要完成支付只需要1张, Q [ i ] [ j ] = 1 Q[i][j]=1 Q[i][j]=1。第 j j j个面值的货币 v j v_j vj​>需要支付的金额 i i i, 此时问题的解与 j − 1 j-1 j−1是一样的。 Q [ i ] [ j ] = Q [ i ] [ j − 1 ] Qleft[i ight]left[j ight]=Qleft[i ight]left[j-1 ight] Q[i][j]=Q[i][j−1]。（比如要支付的金额是5元，这货币面值是10元，显然咱们不能做赔本买卖，这是自然就会想到用更少的面值的货币进行交易，问题与上一阶段是同解的）第 j j j个面值的货币 v j v_j vj​for(j=1; jint n,i,v[10],money;cin >> n; // 我们钱币面值有n种for(i=1; i> v[i];cin >> money; cout