作者anllin (曲辰)
站内Prob_Solve
标题[问题] 关於预算分配或投资组合选择的演算法
时间Tue Jul 7 01:23:31 2009
小弟非资工相关背景
在写研究所作业遇到一个小问题
我想说不定在这个领域已经有个最佳的演算法只是我不知道而已
所以来PO版问问
请高手指点一下
好 问题如下:
假设有预算100
提案(A)61 (B)48 (C)24 (D)20 (E)8
如何选择提案使总金额最接近预算上限
我知道最简单的方法俗称 Greedy Algorithm
就是先将所有提案照降幂排列
然後从头开始挑 直到不超过上限为止
但是在这个例子当中
GA会挑到(A)(C)(E) = 93
如果跳过(A)的话反而可以选到(B)(C)(D)(E) = 100
显然Greedy Algorithm不是最佳的方法
如果反过来以升幂排列
也同样可以做出令这个演算法失败的例子
所以
到底有没有这方面的研究已经提出了最佳方法了呢?
还请高手指点一下
有看到版规禁止作业文
我老实招来 这虽然是作业的一部分 但不是全部
学术嘛 本来就是在别人已有的基础上发展自己的理论
所以才想如果有现成的可以用就不必自己从头做了
如果这个问题太简单太基本
也请不要鞭太大力 ><
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 158.143.213.88
1F：推 chrisdar:01背包问题 07/07 03:39
2F：→ netsphere:同楼上用DP解决 07/07 07:27
3F：→ anllin:啊 不才问一下 DP是什麽的简称啊? 只辜"DP"辜不到东西啊.. 07/09 02:20
4F：→ uptonsun:Dynamic Problem 07/09 16:46
5F：→ anllin:似乎是Dynamic Programming 已找到资料 感谢楼上诸位 07/09 20:36
6F：→ hannibal0416:你的文已经写了Dynamic Programming了@@ 08/18 13:23
7F：→ hannibal0416:说错是贪婪法则@@贪婪法就是找出所有解取其最佳 08/18 13:25
8F：→ hannibal0416:就是动态程式规划的一种 08/18 13:25
9F：→ netsphere:greedy method 跟 DP 好像不太一样吧 08/18 19:20