[問題] 關於預算分配或投資組合選擇的演算法
看板Prob_Solve (計算數學 Problem Solving)作者anllin (曲辰)時間15年前 (2009/07/07 01:23)推噓1(1推 0噓 8→)留言9則, 5人參與討論串1/1
小弟非資工相關背景
在寫研究所作業遇到一個小問題
我想說不定在這個領域已經有個最佳的演算法只是我不知道而已
所以來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
推
07/07 03:39, , 1F
07/07 03:39, 1F
→
07/07 07:27, , 2F
07/07 07:27, 2F
→
07/09 02:20, , 3F
07/09 02:20, 3F
→
07/09 16:46, , 4F
07/09 16:46, 4F
→
07/09 20:36, , 5F
07/09 20:36, 5F
→
08/18 13:23, , 6F
08/18 13:23, 6F
→
08/18 13:25, , 7F
08/18 13:25, 7F
→
08/18 13:25, , 8F
08/18 13:25, 8F
→
08/18 19:20, , 9F
08/18 19:20, 9F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
