买东西，如何实现不找零的算法；(50分)

青

青云

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #1

比如你做公交车，必须自带零钱；司机不会给你找钱的；
假如公交车的价格是90元(实际不会这么高，这是为了举例)，那就你带上能够正好凑出90元的零钱；
至于你是一个50元，两个20元；还是9张10元；这个倒无所谓；关键就是没有“找零”的机制；
假如现在你身上带上若干现金；也许能凑出90元，也许不能凑出(实在凑不出，你就想办法在其他地方化钱)；
如果，我们自己判断，估计不是难事；但是让电脑通过程序找。我觉得就是一个麻烦事。
当然，算法也许不是特别难，只是没有做过而已。
如果对这方面有研究的朋友，希望能用delphi提供一个算法。

 

青

青云

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #2

http://bbs.2ccc.com/topic.asp?topicid=307250
http://www.math.org.cn/forums/index.php?&act=ST&f=37&t=62590
http://www.math.org.cn/forums/index.php?act=ST&f=26&t=62631

 

青

青云

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #3

http://www.itpub.net/thread-1079819-1-1.html

 

P

Passion

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #4

贪心算法？

 

K

kinneng

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #5

先将钱的面值都做在数组，并且排序，然后循环比较
比如你有 50 20 20 10 5
那么数组就是 [0][50][20][20][10][5]，[0]是方便循环程序用统一的公式，当成首个中间结果。
先比较 0+50 是否大于 90，结果50小于90
50就通过，中间结果等于50
然后比较50+20是否大于 90，结果50+20小于90
20又通过，中间结果等于70
然后又比较70+20是否大于 90，结果70+20等于90
20通过。
反过来由小到大比较，也是可以的。
先比较0+5是否大于90，不大于
再比较5+10是否大于90，不大于
...
很简单了

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #6

不限制所带钞票数最少的话可以带1w张一元的,能解所有1w以内的.

 

青

青云

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #7

kinneng提供的这种算法是比较容易想到的。
就像做除法运算那样，从高到低一位位的算下去；
但是实际上，严格的来说，有很大的漏洞；
我举例(为了说明情况，假设人民币各种面值都有)：
如果要凑100元；
身上带有 ：一张50元，2张30元，2张15元 ，2张10元；
按照从大到小取：
只能是：50+30+15+10=105 没法凑到100元，所以电脑只能认为没法正好凑出100元；
而实际可以跳过那两张15元，直接是：50+30+10*2=100 正好凑出100元；
关键是你如果通过程序，让它能够“跳开”那两张15元！！！
这就是需要程序有一定的“智能化”；而不是“傻傻”的就知道排序去取数据；
我感觉是用一种回归算法，类似于蚂蚁找迷宫出口，先按照一定原则走，走不通退回一步，再走其他路径；再不通，退回两步；就是一个递归算法；
这个算法，我感觉有点类似于 “数独”游戏的算法，但也不太像；跟贪婪算法有点形似，但本质不一样；

 

P

Passion

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #8

楼上说的就是贪心算法吧，主要是回溯。

 

青

青云

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-01

• #9

呵呵，就算是贪心算法吧。

我对贪婪算法的形象描述是这样的： 一栋房子失火了，这时候一个人冲进去尽量抢出最值钱的东西，但是总重量是有限制的，比如最多100斤，
所以这个人必须权衡在那么多的东西里面，如何拿出最有价值的100斤的货物；
既然很多人都认为是背包(贪心)算法，那就姑且认为它是吧，细想一下，
也确实很相似，贪婪算法是要取100斤内max(sum(价值)) ；而我这个是，正好凑成来100斤重的货位；都有回溯的原则，而且这个算法好像要比背包简单。
但是究竟如何实现呢？

 

J

jieking

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-02

• #10

我也来凑个热闹学习一下!

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-02

• #11

就是从数组中选数字求和达到指定值的问题，请参考LeeChange兄的回答：
http://www.delphibbs.com/delphibbs/dispq.asp?lid=2293872

 

F

Flashcqxg

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-03

• #12

看版主的吧，很多地方都有，呵呵，我也受了大家的帮助。
过段时间全部结贴了。

 

K

kinneng

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-04

• #13

楼主说的有道理

 

青

青云

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-11-04

• #14

参考creation-zy 朋友提供的：
“
就是从数组中选数字求和达到指定值的问题，请参考LeeChange兄的回答：
http://www.delphibbs.com/delphibbs/dispq.asp?lid=2293872
”
我整理出来了一个程序：
做了个demo演示程序，运行效率非常高；
大家可以看看效果：
程序下载地址：
http://www.daizhicun.com/dmx/dai/OutMatch.rar
截图：
http://www.daizhicun.com/dmx/pic/OutMatch.JPG
主要代码：
http://www.daizhicun.com/dmx/dai/OutMatch.txt
其实我最终的目的，是要把这段delphi代码 转换成 pl/sql，在oracle数据库后台实现。呵呵。
这个问题基本解决了！

 

青

青云

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-12-09

• #15

http://www.delphibbs.com/delphibbs/dispq.asp?lid=3934553