立即注册
 找回密码
 立即注册
搜索
kuso123
发表于: 2038-1-19 11:14:07 | 显示全部楼层



我國 1953 年發行的第二套人名幣有三元紙幣。
这个事儿不应该打上经济学的标签,其实应该打上算法、计算机的标签。
首先说俩关键词:贪心算法,贪心选择性。所谓贪心选择性,是指所求问题的整体最优解可以通过一系列局部最优的选择来得到。货币面值理论上设计出什么数字都行,但是目前各种货币几乎都是1,2,5,10这样的设计,一个重要原因是要让大家使用起来方便。现在举一个例子:


小明去打酱油,给售货员十元,售货员找钱1.4元。小明显然不希望找回来的全是一角的硬币。假设售货员各种面值钱币充足。为了以最少的硬币(纸币)数找给小明1.4元,售货员只需要从能用得上的最大面值开始给小明就可以了。于是售货员先拿出1元,然后拿出两张两角,任务完成。
这种策略就是贪心算法。为了获得全局最优解,在解决问题的过程中,每一步都采取当前局部最优解。但是每一步都采取局部最优解就能保证获得全局最优解了吗?显然不能。因此一个问题能不能采用贪心算法求解,要首先证明该问题具有贪心选择性质。如果一个问题具备贪心选择性,则该问题可以使用贪心法求解。


小明去打酱油,给售货员十元,售货员找钱1.4元。小明显然不希望找回来的全是一角的硬币。假设售货员各种面值钱币充足。为了以最少的硬币(纸币)数找给小明1.4元,售货员只需要从能用得上的最大面值开始给小明就可以了。于是售货员先拿出1元,然后拿出两张两角,任务完成。
这种策略就是贪心算法。为了获得全局最优解,在解决问题的过程中,每一步都采取当前局部最优解。但是每一步都采取局部最优解就能保证获得全局最优解了吗?显然不能。因此一个问题能不能采用贪心算法求解,要首先证明该问题具有贪心选择性质。如果一个问题具备贪心选择性,则该问题可以使用贪心法求解。


货币面值采用1,2,5,10的设计,即是为了保证贪心选择性。还是上面的例子,假设现在加入了面值为七角的钱币。这样贪心选择性就被破坏了:根据贪心法售货员找给小明三张纸币(一元,贰角,贰角)。而全局最优解是两张(七角,七角)。
加入面值为三的钱币比加入七要好一些,因为加入三不会破坏贪心选择性。但是加入三也带不来什么优势,即没法进一步降低找钱的总张数(除了3这个数能由两张降为一张……)。反而加入三还会增加问题的复杂度,让人从无脑的贪心法变得一下需要考虑是否使用三来代替获得更优解。根据奥卡姆剃刀原则(若无必要,勿增实体),既然加入三没什么意义,不如就不要,还能省下一些印钞成本。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
跳转到指定楼层
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表