作者HowLeeHi (處處留心皆正妹)
看板C_and_CPP
標題[問題] 任意數加總的演算法
時間Wed Jan 13 17:40:18 2021
開發平台(Platform): (Ex: Win10, Linux, ...)
Linux
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
GCC
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
none
問題(Question)：
請問N個隨機整數，任意加總找最接近X的演算法
有沒有什麼關鍵字呢?
假設有
22,1,8,37,28,15....
然後任意數加總 最接近但不超過50
我目前是把數字先排序
再用類似greedy的方法
從最大或最小值開始累加
但我發現這樣並不是最優解
請問有沒有關鍵字可以提示一下呢?
thanks!
--
以前的人說世界是平的,往海平面的一端不斷的游過去
最終你會掉進世界的盡頭，直到哥倫布推翻這個說法.
以前的人說太陽是繞著地球轉，直到哥白尼和伽利略的出現
才知道其實我們都是繞著太陽轉.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.234.242 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1610530824.A.575.html
1F：→ kobe8112: 您是否在搜尋: 0/1 背包問題 01/13 18:01
2F：→ HowLeeHi: 感謝1F...我居然忘了這個經典問題 01/13 18:10
3F：推 kendegi: 感覺也可以用DFS(?) 01/14 21:10
4F：推 ucrxzero: 只要不是dp 都是窮舉 01/15 12:18
5F：推 ddavid: 樓上是想講一般論還是單指這題？ 01/15 15:23
6F：→ MartinJ40: dp本質也是窮舉 只是比較有效率 複雜度是NP-complete 01/15 15:32
7F：推 DerLuna: 直覺是要爆搜... 01/17 23:04
8F：→ atoi: N值最大為何呢？ 01/18 21:14