作者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