小超市老板的两个简单需求的实现；

显示全部楼层 · 2007-10-20 08:38:44

第一个需求：
比如小店营业每天8小时，想找出当日盈利最高的一个小时时间段(比如是 8:57~9:57是最高峰)；
比如数据如下：
时间
盈利
.....
8:29:3120元
8:29:5730元
8:31:2317元
......
这个需求看似很简单，但是想通过sql语句实现，感觉很难的；
好像这样些：
select * from (
select a.时间,a.盈利 ,
(select sum(b.盈利) from 流水表b where b.时间 between a.时间 and a.时间+1小时) as 1小时内盈利
from 流水表 a) c
order by 1小时内盈利desc
取第一条记录对应的时间就是最高盈利的一小时内的起始时间；

以上的语句，理论上是可以实现，但是我觉得效率太低了；
我非常希望能用上 sum（盈利）over ( order by 时间) ，这样效率高些；但是考虑好久，好像没法用上分析函数；

第2个需求：

有个顾客来该小店买货，比如总价为27元；

这个顾客可以有很多种付账的组合：比如给老板一张20元，一张10元，让老板找回3元；
也可以给一张50元，让老板找回23元；
.....
当然，感觉最好的就是，不要让老板找钱，这样交易大家都省事；
比如直接付给老板：一张20元，一张5元，一张2元等等；
但是这个”不找零“的sql算法该如何实现呢？
加入该顾客身上的钱是(从大到小)：
100元2张
50元 4张
20元7张
10元 5张
5元2张
2元1张
1元 4张
想凑成 ”不找零“的27元组合非常多；
但是如何通过pl/sql 来匹配找出来呢(感觉要用到递归，贪婪算法等，如果这样直接在pl/sql里用存储过程实现还挺有难度的)
比如写一个游标，让钱从大到小或从小到大排序，怎么也刚好凑出27元；
这个算法太困扰我了；
实际上我是做自动立体仓库的；
客户出货是，比如要出27件货，仓库里各个托盘上分别有100件/托，50件/托.......若干；
我要做个算法，尽量匹配出几个托盘刚好全部出库27件；
这个算法很实用，可是我一直找不到好的方法，
希望高人指导。
[ 本帖最后由 qingyun 于 2008-11-1 08:59 编辑 ]

千问 · 2007-10-20 08:38:44

用自连接，时间作连接条件再分组合计。

千问 · 2007-10-20 08:38:44

第二个就是个“背包问题”，可以搜索一下。

千问 · 2007-10-20 08:38:44

原帖由 newkid 于 2008-10-31 23:53 发表
用自连接，时间作连接条件再分组合计。

newkid朋友，非常感谢你的回复，我上次发了一个帖子，关于仓库出库并发的问题；
我在你的回帖种学到了
update ... set ..where ..returning .... into ....
这样写法，收益匪浅；

第二个问题，好像是个经典问题，但是和贪婪(背包)算法也不太一样；
贪婪算法的例子和这个有一点点相似，但实质好像是不一样的；
贪婪算法的形象描述是这样的：一栋房子失火了，这时候一个人冲进去尽量抢出最值钱的东西，但是总重量是有限制的，比如最多100斤，
所以这个人必须权衡在那么多的东西里面，如何拿出最有价值的100斤的货物；
而且，就算贪婪法可行，但是贪婪算法感觉挺低效的，要把所有的货物都要检索，而且还要来回检索很多遍，才能得到最佳结果；
这个如果单纯用类似教科书上C语言写，考虑的比较单纯；
如果通过数据库层面实现，又要考虑并发异常问题；
[ 本帖最后由 qingyun 于 2008-11-1 00:09 编辑 ]

千问 · 2007-10-20 08:38:44

呵呵有空多交流，我在这里也学到了很多！

千问 · 2007-10-20 08:38:44

原帖由 newkid 于 2008-11-1 00:07 发表
呵呵有空多交流，我在这里也学到了很多！
写了多年的软件，大部分精力都是和pl/sql打交道；
通过存储过程或包提供给客户端的调用；
所以的业务的实现基本都在pl/sql上实现；一些简单的算法，基本可以通过循环游标，order by ,over分析函数等处理手段搞定；
但是一旦用到一些很有算法感的处理，就发现很难，感觉就是很多扫描，而且还重复对一样东西扫描多次，比如退化算法，遗传算法；
实现起来非常麻烦，可以考虑把所有满足的DataSet先拷贝到pl/sql表或多维数值组里；在通过传统的C语言的经典算法实现；
没有实际试过。
在说的惭愧些，就根本没写过那种很有算法感的程序，所以对付这些复杂算法问题，感觉还是挺束手无策的。

千问 · 2007-10-20 08:38:44

你的目标是什么呢？搭配次数最少还是差额最少？
比方说你要出货90件，10*9次好呢，还是100一次再还回10好？
关于并发的问题上次也讨论过，其实你这些搭配都是理论上的，不会影响实际库存，那么你只要保证同一时刻不对同一个托盘运行该过程就行了，最简单的办法就是对该库区的该商品上一个行锁。

千问 · 2007-10-20 08:38:44

还有在实际生活中库存不可能很分散的，以计算机的能力穷尽其组合，必要时反复扫描也不在话下，不必钻牛角尖苛求最佳算法。那些理论上最佳的算法可能实现起来更困难，代码更难维护，而提升的效率却有限。

千问 · 2007-10-20 08:38:44

你说的：比方说你要出货90件，10*9次好呢，还是100一次再还回10好？
很有道理。
不过，我现在手上做的一个项目，客户的明确要求是：不允许出现“还回”的情况，所以宁愿是前者；
万一，真的凑不到90，那么就吧那个100的拿出来，拆成90和10，再经过重新打包入库，这时候才可以出(这是迫不得已，尽量不要出现这个情况)；
不管客户流程是不是合理，他就是这么要求的。
可以这么理解吧。比如你做公交车，必须自带零钱；司机不会给你找钱的；
比如公交车的价格是90元(实际不会这么高，这是为了举例)，那就你带上能够正好凑出90元的零钱；
至于你是一个50元，两个20元；还是9张10元；这个倒无所谓；关键就是没有“找零”的机制；

那么加入我是一个乘客，身上带上若干现金；也许能凑出90元，也许不能凑出(实在凑不出，你就想办法在其他地方化钱)；
如果，我们自己判断，估计不是难事；但是让电脑通过程序找。我觉得就是一个麻烦事。
当然，算法也许不是特别难，只是没有做过而已

你说的：最简单的办法就是对该库区的该商品上一个行锁。
这个我也是这么认为的。不过这是个比较“严格”的一招；
假如仓库里有10万个货位，而且整个仓库就一种产品，那么假如出库作业也很繁忙，如果做这种最严格的锁，就会导致互相干扰；
比如很多时候，我只要出1个货位的产品就够了，但是为了防并发造成脏数据，却把另外的9999个货位库存锁住，代价感觉有点大了；

http://www.delphibbs.com/delphibbs/dispq.asp?lid=3927406
http://www.math.org.cn/forums/in ... mp;f=37&t=62590
[ 本帖最后由 qingyun 于 2008-11-1 09:42 编辑 ]

千问 · 2007-10-20 08:38:44

第二个需求感觉好奇怪，你怎么知道用户身上有哪些面值的钱呢？