需求通用算法
需求通用算法：（要求顾客最大化原则）
商场搞活动送赠券:
购商品A,现金100送10券一张，200送30券一张,张数不封顶
购商品B,现金200送30券一张, 400送65券一张,张数不封顶
购商品C,现金200送20券一张，500送60券一张,张数不封顶
产生的赠券通用
现顾客购买商品A 200元,商品B 450,商品C 1200,
支付方式：1000元赠卷，850元现金，问850现金应生成
各种券几张(券面金额相同算一种)
问题点数：50、回复次数：32Top
1 楼polestarxu（一点星光）回复于 2006-08-30 16:14:45 得分 0
upTop
2 楼j9988（j9988）回复于 2006-08-30 16:21:17 得分 0
1.先算出每100元奖的比例,比如:购商品B,400送65券一张 奖的比便最高. 首先考虑,其次是A B的200送30 再次是C 500送60券一张
2.看看购买的数字是否达标.从高拿到低,这样得出:
购商品B 400送65券一张
购商品A 200送30券一张
购商品C,200送20券一张
Top
3 楼tzlhr（泥土）回复于 2006-08-30 16:30:30 得分 0
比例高是不错的，但是还要考虑现金的总额，
例：商品A 80 送 20 20/80=0.25
商品B 70 送 15 15/70=0.21
按比率,2张20的券,则40，但实际应生成3张15的券45例Top
4 楼ww3347（新来的）回复于 2006-08-30 16:32:43 得分 0
j9988算法是很容易想到的办法，但是不对，还要考虑现金全部分配出去的问题。
假设现金200送180，300送300，400送450。顾客花500元。
按你的算法，只能取400送450，剩余100现金浪费了。
实际取现金200送180，300送300，可得券480。此情况下是最优的。
只负责挑错：）
Top
5 楼j9988（j9988）回复于 2006-08-30 16:44:11 得分 0
有道理!没想到.
那只好穷举了.跟据顾客购买的每种商品,金额.在客户购买本商品现金额度范围内.循环穷举.找出最大的金额.Top
6 楼j9988（j9988）回复于 2006-08-30 17:05:29 得分 0
这得花点功夫,多一点实例.穷举加判断.
850元现金如何根据200 450 1200分配.就是A分配现金封顶200 B封顶450,C封顶850.
这样:
A分配现金封顶200 只有两种方案:现金100送10券一张X2，或 200送30券一张X1
B分配现金封顶450 现金200送30券一张X2 或 400送65券一张
C分配现金封顶850 现金200送20券一张X4 或 500送60券X1+200 送20券X1
根据以上ABC可能的方案穷举.得出最高金额.
Top
7 楼j9988（j9988）回复于 2006-08-30 17:08:47 得分 0
就是先算A B C最多可出那种几张奖券,然后这几种来穷举分配.得出最大金额的分配方案.Top
8 楼ww3347（新来的）回复于 2006-08-30 17:11:07 得分 0
继续：）怎么穷举？
注意：不是你列举的6个东西的组合。Top
9 楼j9988（j9988）回复于 2006-08-30 17:18:20 得分 0
就是先根据购买商品的金额,算出每种商品可能的分配的现金数,
比如你只购A200元.但现金是850元,它不可能在里面拿850元奖券吧.最多只能分它200元.
这样它有可能出现的是100元可最多出2张 200元可最多出1张.
依此类堆算出B C 最多出的券别张数
比以上结果的限制范围内来穷举.Top
10 楼toto1980（^涛^）回复于 2006-08-30 17:19:35 得分 0
1.付款金额最大可能分配出去，计算可得奖券
2.j9988(j9988)的方法计算可得奖券
两者取最大Top
11 楼j9988（j9988）回复于 2006-08-30 17:21:43 得分 0
穷举的可能性有:
1. A 100X2 +B 200X2 +C 200X2
2. A 100X1 +B 200X2 +C 500X1
3. A 200X1 +B 200X2 +C 200X1
...........
同时各算出以上的奖券金额．取奖券金额最大的一组．Top
12 楼specialsoldier（雪地撒野~噢姐姐,我要回家）回复于 2006-08-30 17:29:19 得分 0
j9988算法有问题:
1,上面说了要考虑现金全部分配的问题.可能给了比例高的,回余一些现金.但给比例低的,现金用的多.这样现金的利用率也算有个影响因素.
2.还要考虑的是,这个所谓的比例是不定的,可能买100送10,买200就送180,这样的分段比例需要更多的判断来支持.
穷举肯定可以,但是有其他方法的.
Top
13 楼ww3347（新来的）回复于 2006-08-30 17:32:25 得分 0
穷举的可能性有:
1. A 100X2 +B 200X2 +C 200X2
2. A 100X1 +B 200X2 +C 500X1
3. A 200X1 +B 200X2 +C 200X1
...........
同时各算出以上的奖券金额．取奖券金额最大的一组．
－－－－－－－－－－－－－－
嘻嘻，穷举一下看看一共多少种。这个穷举算法怎么写？Top
14 楼ww3347（新来的）回复于 2006-08-30 17:34:46 得分 0
1.付款金额最大可能分配出去，计算可得奖券
2.j9988(j9988)的方法计算可得奖券
两者取最大
－－－－－－－－－－－－－－－
400 送 450
300 送 300
200 送 180
100 送 90
95 送 95
500 元现金，送吧：）Top
15 楼j9988（j9988）回复于 2006-08-30 17:38:57 得分 0
首先,
我已经说过了,先算出每种可能出的券别.这样再穷举.并不是说一定要出现.只是可能出现.
这种穷举用SQL不难.只要数一个while循环就行.具体算法当然得根据奖券分类来做具体的优化.
比如出现1元奖1毛.你买10万元现金那不惨了.
Top
16 楼j9988（j9988）回复于 2006-08-30 17:43:01 得分 0
两者取最大
－－－－－－－－－－－－－－－
400 送 450
300 送 300
200 送 180
100 送 90
95 送 95
500 元现金，送吧：）
如果500元现金分配买这一种商品.且这种商品有这么多方案.很好算的.这不是问题Top
17 楼specialsoldier（雪地撒野~噢姐姐,我要回家）回复于 2006-08-30 17:44:40 得分 0
比如出现1元奖1毛.你买10万元现金那不惨了.
-----------------
具体的优化说得也是.不过要真是出现1元奖1毛也不惨的.先将其他所有段的回报率算出来,当大于0.1的时候就不考虑1元奖1毛.要小于等于就换吧...因为此时1元是最小金钱单位
要出现1元奖1毛,3毛奖1分就爽歪了Top
18 楼j9988（j9988）回复于 2006-08-30 17:46:07 得分 0
你说得对,是啊.得根据情况做具体的优化.考虑极端情况出现.Top
19 楼j9988（j9988）回复于 2006-08-30 17:46:46 得分 0
不聊天了,得上班.Top
20 楼ww3347（新来的）回复于 2006-08-30 17:47:31 得分 0
j9988老大写个简单的穷举模型来看看，我学习一下：）
那个例子是针对toto1980(^涛^) 提出的方案做的，最优的是 300+95+95 ,既不是你的方案，也不是付款金额最大可能分配出去：）Top
21 楼fattycat（最爱胖猫）回复于 2006-08-30 18:08:09 得分 0
markTop
22 楼aruisi（）回复于 2006-08-30 19:34:38 得分 0
jfTop
23 楼redwoodschu（一觉睡到太阳下山zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz）回复于 2006-08-30 21:50:19 得分 0
这个有点像内存碎片分配的算法。。。
Top
24 楼redwoodschu（一觉睡到太阳下山zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz）回复于 2006-08-30 22:15:13 得分 0
先计算每种商品的每种回馈模式的赠券回报率
再按回报率高低排序，分别是
回报率6.15 B,400送65券一张
回报率6.67 B,200送30券一张；A，200送30券一张
回报率8.33 C，500送60券一张
回报率10 C,现金200送20券一张；A,现金100送10券一张
加权后回报率是7.96
比如最简单的最大化的分配就是
在总金额〈850的情况下，计算出总点券是400*2，一共130点
浪费50元，乘加权后的回报率就是浪费了的点券，是6.3点
130/（130+6.3）就是点券的利用率
顾客最大化原则最后比较的实际上是点券的利用率
不知道这样的想法是否有误，请大家指教
Top
25 楼greenoldman（）回复于 2006-08-30 22:22:31 得分 0
谁有最优算法???
Top
26 楼j9988（j9988）回复于 2006-08-30 23:17:59 得分 0
to ww3347(新来的): 你对楼主的需求只理解一半.
针对你的出题,比楼主的需求简单多了. 况且你所认的为最优方案也是错的.
我随便写一个:
set nocount on
declare @a table(id int identity,m int,p int)
insert @a(m,p) select 400,450
union all select 300,300
union all select 200,180
union all select 100,90
union all select 95,95
declare @all int
set @all=500
declare @i int
set @i=1
declare @b table(id varchar(100),m int,p int,f int)
insert @b select ','+rtrim(id),m,p,1 from @a where m<=@all
while exists(select 1 from @a A,@b B where A.m+B.m<=@all and B.f=@i and A.id>right(B.id,charindex(',',reverse(B.id))-1))
begin
insert @b select B.id+','+rtrim(A.id),A.m+B.m,A.p+B.p,@i+1 from @a A,@b B where A.m+B.m<=@all and B.f=@i and A.id>right(B.id,charindex(',',reverse(B.id))-1)
set @i=@i+1
end
select A.*,B.p as AllPay from @a A,@b B where charindex(','+rtrim(A.id)+',',B.id+',')>0 and B.id in (select top 1 id from @b order by p desc)
--结果应该545元 取400跟95 而不是300,95,95
id m p AllPay
----------- ----------- ----------- -----------
1 400 450 545
5 95 95 545Top
27 楼j9988（j9988）回复于 2006-08-30 23:26:57 得分 0
上面和代码中两处:A.id>right(B.id,charindex(',',reverse(B.id))-1) 应改为:A.id>=right(B.id,charindex(',',reverse(B.id))-1)
所以的结果:
ID m p
--------------- ----------- -----------
,1,5 495 495
,1,4 500 490
,2,5,5 490 490
,2,4,5 495 485
,2,4,4 500 480
,2,3 500 480
,5,5,5,5,5 475 475
,4,5,5,5,5 480 470
,4,4,5,5,5 485 465
,3,5,5,5 485 465
,3,4,5,5 490 460
,4,4,4,5,5 490 460
,4,4,4,4,5 495 455
,3,4,4,5 495 455
,3,3,5 495 455
,3,3,4 500 450
,3,4,4,4 500 450
,4,4,4,4,4 500 450
,1 400 400
,2,5 395 395
,2,4 400 390
,5,5,5,5 380 380
,4,5,5,5 385 375
,4,4,5,5 390 370
,3,5,5 390 370
,3,4,5 395 365
,4,4,4,5 395 365
,4,4,4,4 400 360
,3,4,4 400 360
,3,3 400 360
,2 300 300
,5,5,5 285 285
,4,5,5 290 280
,4,4,5 295 275
,3,5 295 275
,3,4 300 270
,4,4,4 300 270
,5,5 190 190
,4,5 195 185
,4,4 200 180
,3 200 180
,5 95 95
,4 100 90
自已比较吧Top
28 楼j9988（j9988）回复于 2006-08-30 23:30:57 得分 0
楼主的需求比你理解的要复杂得多.
所以我说,要跟据实例做一些算法上调整和改进.Top
29 楼ww3347（新来的）回复于 2006-08-31 09:23:32 得分 0
恩 ，对。我的错了。学到穷举的办法：）
楼主更复杂的一点就是每个类别还有上限，不是全排列？
我举那个例子只是针对这个算法提出的，证明这个算法是不对的。除了穷举，还有没有简单点的算法？
－－－－－－－－－－－－－－－－－－－－－－－－
1.付款金额最大可能分配出去，计算可得奖券
2.j9988(j9988)的方法计算可得奖券
两者取最大
－－－－－－－－－－－－－－－－－－－－－－－－Top
30 楼fcuandy（了此残生.）回复于 2006-08-31 10:19:29 得分 0
只能穷举.
跟那天那人的问题差不多.
表中有 20w 条记录,有字段amount,现在想删除一些数据,使剩下的数据尽可能的接近3000.
其实这两个题的本质是一样的.
不用穷举的话,可以用近似算法,每次取最大可能获得的赠送的办法,但获取的结果并不一定跟理论上可获的的最大值相等. 写法如下:
DECLARE @t TABLE(id INT IDENTITY(1,1),Type VARCHAR(1),Require INT,Amount INT)
INSERT @t SELECT 'A',100,10
UNION ALL SELECT 'A',200,30
UNION ALL SELECT 'B',400,65
UNION ALL SELECT 'B',200,30
UNION ALL SELECT 'C',200,20
UNION ALL SELECT 'C',500,60
DECLARE @Require INT
SET @Require=850
SELECT IDENTITY(INT) ID INTO # FROM sysobjects,syscolumns
DECLARE @x TABLE(type VARCHAR(1),Require INT)
INSERT @x SELECT 'A',200
UNION ALL SELECT 'B',450
UNION ALL SELECT 'C',1200
DECLARE @m TABLE(type VARCHAR(1),Require INT,Times INT,Amount INT)
DECLARE @Rq INT,@Tm INT,@Am INT,@Tp VARCHAR(1)
WHILE @Require>0
BEGIN
SELECT a.*,b.ID Times
INTO #1
FROM @t a
INNER JOIN
(SELECT MAX(a.Amount*b.id) ma,a.type
FROM @t a
INNER JOIN # b
ON a.Require*b.ID <=(SELECT Require FROM @x WHERE a.type=type) AND a.Require*b.ID<=@Require
GROUP BY a.Type) x
ON a.type=x.type
INNER JOIN # b
ON b.id*a.Amount=x.ma
SELECT @Tp=Type,@Rq=Require,@Am=Amount,@Tm=Times
FROM #1
WHERE Amount=(SELECT MAX(Amount) FROM #1)
SET @Require=@Require-@Rq*@Tm
IF @Require>0
INSERT @m SELECT @Tp,@Rq,@Tm,@Am
UPDATE @x SET Require=Require-@Rq*@Tm WHERE Type=@Tp
DROP TABLE #1
END
SELECT * FROM @m
DROP TABLE #
/*结果
Type Require Times Amount
B 400 1 65
A 200 1 30
C 200 1 20
*/
结果说明:
用 400元付 B类 一次,获 65
用 200元付 A类 一次,获 30
用 200元付 C类 一次,获 20
剩余50元没满足任何条件,任意支付.共获得 115
楼主可以将测试数据,比如A类物品购买花400元看看,那么此时就是用400元去付A类物品2次,剩余50元不满足任何条件,任意支付,共获得 125
上面已经说明了,得出的结果并不一定是理论上最大的可获取的值.Top
31 楼fcuandy（了此残生.）回复于 2006-08-31 10:33:35 得分 0
SELECT @Tp=Type,@Rq=Require,@Am=Amount,@Tm=Times
FROM #1
WHERE Amount=(SELECT MAX(Amount) FROM #1)
这句稍稍更正一下,加上 ORDER BY Require*Times DESC
以付最少的钱获得最大的赠送Top
32 楼prcgolf（小鸟）回复于 2006-09-12 14:40:27 得分 0
upTop
