c – 确定硬币组合的算法

发布时间：2020-12-16 03:12:38 所属栏目：百科来源：网络整理

导读：我最近面临着一个编程算法的提示,我不知道该怎么做.我从来没有真正写过一个算法,所以我是一个这样的新手. 问题是写一个程序,以确定收银员的所有可能的硬币组合,作为基于硬币值和硬币数量的变化作为替代.例如,可能有一个4个硬币的货币：2分,6分,10分和15分硬

我最近面临着一个编程算法的提示,我不知道该怎么做.我从来没有真正写过一个算法,所以我是一个这样的新手.

问题是写一个程序,以确定收银员的所有可能的硬币组合,作为基于硬币值和硬币数量的变化作为替代.例如,可能有一个4个硬币的货币：2分,6分,10分和15分硬币.有多少组合等于50美分？

我使用的语言是C,尽管这并不重要.

编辑：这是一个更具体的编程问题,但是如何分析C中的字符串来获取硬币值？他们在文本文档中给出了

4 2 6 10 15 50

(这里的数字对应于我给出的例子)

解决方法

这似乎有点像分区,除了你在1:50中不使用所有的整数.它也似乎类似于bin包装问题,略有不同：

> Wikipedia: Partition (Number Theory)
> Wikipedia: Bin packing problem
> Wolfram Mathworld: Partiton

其实在考虑之后,是an ILP,NP-hard.

我建议一些动态的编程appyroach.基本上,您将定义一个值“余数”,并将其设置为您的目标(例如50).然后,在每一步,您将执行以下操作：

找出可以适合剩下的最大的硬币
>考虑如果你(A)包括硬币或(B)不包括那个硬币会发生什么.
>对于每个场景,递归.

所以如果剩余的是50,最大的硬币是25和10,你会分两种情况：

1. Remainder = 25,Coinset = 1x25
2. Remainder = 50,Coinset = 0x25

下一步(每个分支)可能如下所示：

1-1. Remainder = 0,Coinset = 2x25 <-- Note: Remainder=0 => Logged
1-2. Remainder = 25,Coinset = 1x25
2-1. Remainder = 40,Coinset = 0x25,1x10
2-2. Remainder = 50,0x10

每个分支将分成两个分支,除非：

>剩下的是0(在这种情况下你会记录它)>剩下的是小于最小的硬币(在这种情况下你会丢弃它)>没有更多的硬币留下(在这种情况下,你会丢弃它,因为剩余！= 0)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!