假设我们有五个数字，N，A，B，C，D。我们从数字0开始，结束于N。我们可以通过一定数量的硬币来改变一个数字，具体操作如下：
将数字乘以2，支付A个硬币将数字乘以3，支付B个硬币将数字乘以5，支付C个硬币增加或减少数字1，支付D个硬币
我们可以任意次数以任意顺序执行这些操作。我们需要找到达到N所需的最少硬币数量
因此，如果输入是N = 11; A = 1; B = 2; C = 2; D = 8，那么输出将是19，因为最初x为0。
用8个硬币将x增加1（x=1）。
立即学习“C++免费学习笔记（深入）”；
用1个硬币将x乘以2（x=2）。
用2个硬币将x乘以5（x=10）。
用8个硬币将其增加1（x=11）。
步骤
为了解决这个问题，我们将按照以下步骤进行：
Define one map f for integer type key and valueDefine one map vis for integer type key and Boolean type valueDefine a function calc, this will take nif n is zero, then: return 0if n is in vis, then: return f[n]vis[n] := 1res := calc(n / 2) + n mod 2 * d + aif n mod 2 is non-zero, then: res := minimum of res and calc((n / 2 + 1) + (2 - n mod 2)) * d + a)res := minimum of res and calc(n / 3) + n mod 3 * d + bif n mod 3 is non-zero, then: res := minimum of res and calc((n / 3 + 1) + (3 - n mod 3)) * d + b)res := minimum of res and calc(n / 5) + n mod 5 * d + cif n mod 5 is non-zero, then: res := minimum of res and calc((n / 5 + 1) + (5 - n mod 5))if (res - 1) / n + 1 > d, then: res := n * dreturn f[n] = resFrom the main method, set a, b, c and d, and call calc(n)
登录后复制
Example
让我们来看下面的实现以更好地理解 −
#include using namespace std;int a, b, c, d;map f;map vis;long calc(long n){ if (!n) return 0; if (vis.find(n) != vis.end()) return f[n]; vis[n] = 1; long res = calc(n / 2) + n % 2 * d + a; if (n % 2) res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a); res = min(res, calc(n / 3) + n % 3 * d + b); if (n % 3) res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b); res = min(res, calc(n / 5) + n % 5 * d + c); if (n % 5) res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c); if ((res - 1) / n + 1 > d) res = n * d; return f[n] = res;}int solve(int N, int A, int B, int C, int D){ a = A; b = B; c = C; d = D; return calc(N);}int main(){ int N = 11; int A = 1; int B = 2; int C = 2; int D = 8; cout 输入
11, 1, 2, 2, 8
登录后复制
输出
19
登录后复制
以上就是C++程序：计算使用硬币支付达到n所需的操作次数的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2581691.html
