預算內最高值的算法

我並不完全確定問這個問題的最佳方法（或者做研究以查看它是否已經被回答過）。預算內最高值的算法

給定的數據集，其中的每一項都有一個點值和一美元的價值，我期待生成產生最高總點值，而預算B.

例內停留長度爲N項的列表數據集：

Item Points Dollars 
Apple 3.0  $1.00 
Pear 2.5  $0.75 
Peach 2.8  $0.88

而與此（小）的數據集，說我的預算（B）是$ 2.25，和列表長度（N）必須2.您必須使用固定列表的長度，但不需要使用所有的預算。

很明顯，提供的例子很容易做到，但是如果給定一個更大的數據集，並且N和B的值都更高，那麼我正在尋找一個可以生成列表的算法。困難的時光纏繞着我的頭。

只是尋找一個僞算法，但如果你喜歡任何給定的語言隨時迴應！

這是揹包問題。 https://en.wikipedia.org/wiki/Knapsack_problem – 2015-11-04 22:45:17

它似乎是揹包問題。非常感謝鏈接！ –

請注意，就困難問題而言，揹包非常容易。如果點數/美元比率存在顯着變化，那麼整數程序求解器可能會合理快速地找到最優解。 –

我相當積極的一點是，這可以歸結爲一個NP完全問題，因此它並不真正值得開發一個過程，它總是會給你'正確'的答案，因爲許多人已經嘗試過但沒有做到這一點高效地處理大型數據集。但是，您可以使用更高效的逼近技術，儘管它不能保證給出正確的答案，但許多流行的逼近算法都能夠實現高度的準確性。

希望這可以幫助你:)

2015-11-04 22:47:29 numX

這個問題是NP完全（NP和NP-硬），這意味着，到現在爲止，沒有算法發現，解決了一個多項式時間量（這個問題多項式到輸入大小），如果你找到一個算法，你就可以解決計算機科學中最大的問題之一（P = NP），你至少會帶來一百萬美元的回報。

如果您滿意的逼近，我會建議貪心算法：

2015-11-04 22:52:54 PaulProgrammerNoob

回答