優化算法問題

這對於那些訣竅傢伙來說可能是一個簡單的問題。但我無法自己弄清楚。優化算法問題

假設有大量的對象需要我選擇。每個對象都有兩個已知變量：成本和收益。我有一個預算，比如說1000美元。如何才能找出我應該購買哪些物品，以便在給定預算內最大限度地提高總收益？我想要一個數字優化解決方案。謝謝！

2011-03-29 ZNN

收益是貨幣嗎？或者你是否僅僅在某些任意單位的「利益」中表達利益。如果僅僅是「利益」，@Carl就是錢的現貨。如果收益是貨幣，那麼你正在尋找不同的情況，因爲收益意味着你會改變你的平衡，因此你可以買得起的成本。 – corsiKa 2011-03-29 23:45:45

我沒那麼想。這會讓問題變得更加複雜。 – ZNN 2011-03-30 01:33:54

你的問題叫做「揹包問題」。你可以閱讀更多關於wikipedia page。將原始問題的術語翻譯成維基百科文章的術語，您的問題的「成本」是揹包問題的「重量」。你的問題的「好處」是揹包問題的「價值」。

找到一個確切的解決方案是一個NP完全問題，所以如果您有很多對象可供選擇，請爲慢結果做好準備！

2011-03-29 23:39:30

謝謝！揹包問題恰恰是我原來的問題。但是，我的「真正的問題」比這個標準問題有點複雜。我閱讀了有關揹包問題（動態編程解決方案？）的解決方案，並認爲它可能無法解決我的「真正問題」。我將下面的實際問題描述如下。希望你能給我一些關於如何解決它的建議。 – ZNN 2011-03-30 01:44:24

假設每個項目的「價值」不是恆定的。所選項目的總「價值」是所選項目的兩個變量（x，y）的函數：Sum（x_i）/ Sum（y_i）。鑑於總重量的限制，如何選擇物品以獲得最高價值？有關這個問題的任何建議？ – ZNN 2011-03-30 01:57:50

您可能還會考慮Linear Programming。從MathWorld：

簡單地說，線性規劃是某些設定的使用線性數學模型的約束基礎的結果的優化。

2011-03-30 02:16:25 xan

是的，如前所述，這是揹包問題，我會選擇使用線性編程。

這個問題的關鍵是存儲數據，以便您不需要重複計算多次（如果有足夠的內存可用）。線性規劃有兩種常用的方法：自上而下和自下而上。這是一個自下而上的問題。

（一般情況下）查找基本情況值，選擇什麼是最適合小案例的最佳對象。然後在此基礎上構建。如果我們允許自己花更多的錢，那麼對於這個小的貨幣增量來說，最好的組合是什麼。可能會採取更多的東西，你以前有過，採取一個新的對象，並取代舊的，採取另一個小物件，仍然會讓你在你的預算等。

就像我說的，主要想法是不重新計算值。如果你遵循這種模式，你會得到一個很高的數字，並發現爲了購買價值數十美元的商品，最好的解決方案是將你對兩個小案例的結合起來。

2013-04-23 04:14:20 mNeubauer

回答