[問題] 關於預算分配或投資組合選擇的演算法

[anllin (曲辰)]

小弟非資工相關背景
在寫研究所作業遇到一個小問題
我想說不定在這個領域已經有個最佳的演算法只是我不知道而已
所以來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
推 chrisdar:01背包問題
→ netsphere:同樓上用DP解決
→ anllin:啊  不才問一下 DP是什麼的簡稱啊? 只辜"DP"辜不到東西啊..
→ uptonsun:Dynamic Problem
→ anllin:似乎是Dynamic Programming 已找到資料 感謝樓上諸位
→ hannibal0416:你的文已經寫了Dynamic Programming了@@
→ hannibal0416:說錯是貪婪法則@@貪婪法就是找出所有解取其最佳
→ hannibal0416:就是動態程式規劃的一種
→ netsphere:greedy method 跟 DP 好像不太一樣吧