QUOTE(jy-laji @ Dec 30 2021, 10:30)

其实Greedy algorithm是个十分简单粗暴的算法了。对于随机问题的平均结果,我觉得应该足够好了。
但是效率分析就极其困难了。比如,说不定有可能设计出来一组数据,实际的最优解是 n,但这个算法得到的结果最多只能达到 lg n 的数量。而另一种算法则可以证明一定能达到至少n/2的数量。
组合优化问题里这种坑太多了,很困难的,不投入个几年的钻研是很难有深刻理解的。
QUOTE(SoDick @ Dec 31 2021, 00:03)

把所有可能列出来不费时(考虑在C++里做尾递归优化),不过光四款就有90种可能,你有四五十款的话可以列出上
种可能,之后用贪婪算法也会很费时吧。
我的建议是分拆成几组,要求每组最后产生的remain不超过一定范围,分别计算。
貪婪算法也不錯,我開始用這個思路來作解了,
畢竟這裡的實際情況裡額較大的款式其數量也比較少,
也就是先消滅大面額可以更快的減少總款式數量,從而簡化計算難度。
目前我的第一步就是先找出能消耗少量且大面額並盡量貼近目標5000的組合。
我把現有的數據複製上來,大家可以試試算算看,
不過不用實際算出結果來,
因為明早又會增加新的“點數卡”,今晚的最優解到明早就不適用了。
追加條件:
每個組合裡面必須包含一張面額不少於2000的點數卡。
QUOTE
Value,Quantity
2656,1
2674,1
2067,32
2756,1
2156,20
2447,10
2022,23
2037,20
2397,17
2517,25
2236,15
2098,14
499,84
441,34
800,36
599,27
699,30
594,21
529,21
400,18
999,67
412,30
669,16
758,11
1050,10
894,8
899,7
494,20
1114,6
967,5
1278,4
858,4
806,4
1897,3
842,3
2302,2
404,1
447,1
794,1
790,1
1001,1
1274,1
1217,1
1530,1
1512,1
536,1
858,1
1050,1
922,1
1740,1
1428,1
799,26
719,14
539,23
2997,10
This post has been edited by susancat: Dec 30 2021, 19:35