最大化整數子集的網絡算法

Question

我目前正在研究模擬幾種不同類型網絡的寵物項目。其中之一需要一些特定的條件，直到現在，我只是蠻力。然而，它不能很好地擴展，所以我試圖有效地做到這一點，但是這個算法真的讓我失望了！我會盡量描述這個問題。

給定一組整數X和一個整數k，找到的子集X Y的是，在X上的每個值最大化M的總和：

M（S）= Y中的最大值，使得它小於或等於s。由於M（2）= 2，M（4）= 4，所以對於{2,4,5}和k = 2，解值爲{2,4}，其值爲2 + 4 + 4 = 10和M（5）= 5

我的直覺的是，該解決方案是一種動態編程算法，但我可能是遙遠。任何幫助將不勝感激！

Answer 1

這是一個動態的程序問題的解決方案 - 我不知道這是否是你的，因爲我不知道的，你所寫的內容細節，但它可能是。

排序組數字和繪製與x軸給出以排序的順序和y軸給出數目的數目的偏移的曲線。曲線下方會有一些區域。

您的點數有限，通常比該集的成員數少。您可以使用這些點中的每一個來標記集合中的一個點，從而標出曲線上的一個點。

在曲線下繪製直方圖。在每個標記點處，從該點開始的一條線向右，因此線完全位於曲線下方。每條這樣的線都會延伸到達到下一個標記點​​的x值，此時會有一條線上升到新的標記點。

面臨的挑戰是，然後選擇指向標誌下方的橫線從標記點右側要最大化的區域。這是直接的動態編程。如果您最多可以選擇k個標記點，那麼在直方圖的每個點上可以使用0,1,2，... k標記點（可能包括該點）計算出該點左側可以覆蓋的最多區域。你可以通過參考你已經爲左邊的點求出的答案來找出每個點的答案。最重要的問題的答案是整個問題的答案。

要展開這樣的：假設你正在爲期末最大區域制定出最佳的解決方案，以抵消10.對於每個值j 0..k考慮採取在0，1，2，3結束之前的最佳解決方案..並且保持那個點的高度，而不需要引入新的路線。這個區域的總面積是直到那一點的面積加上他們在那個點上的任何高度乘以到該點的距離所獲得的新區域。同樣考慮這樣做，但是在這一點上使用額外的標記點，所以總面積是j-1點最高達到最佳值的最佳解決方案的面積。點7加上從點10到點7的高度的距離。通過考慮這兩種可能性，可以使用0,1,2，... k標記點在點10處求出最佳解。

我認爲這些問題是相關的，因爲對於每個點，標記與否，它對直方圖貢獻的面積取決於它上面的線的高度，它是最大標記點的高度，不大於點我們目前正在考慮。

要做到這一點，你需要通過給每個點使用至多爲k的最佳解決方案所覆蓋的區域KN元素的數組標記點達到那裏。使用這種大小的額外數組來記錄導致這種最佳解決方案的決策也很方便，因此您可以追溯回答。這有一個大約kn^2的成本，因爲在每個n點你需要計算k值，並回顧以前的所有點。我懷疑你可以通過改變你在每個點存儲的定義來減少它，使其像O（kn）一樣，所以你永遠不必回顧以前的一點。如果你能做到這一點，你可以通過只存儲幾個中間點並在較小的部分再次解決問題來追溯，從而節省商店的時間，但是你需要拼命地缺乏存儲來實現值得一提。

Answer 2

我的回答是其中一個比另一個非常類似：

算法我的建議是開始有K = N，下令所有號碼，並保持刪除號碼，直到達到您選擇所需K.數在每個步驟中刪除，代表最低損失的人。

例子：假設你有數字：

3，7，9，13和19

問題是K = 3

你開始在K = 5（所有數字選擇）。

3 + 7 + 9 + 13 + 19 = 51

首先編號，以除去：

如果3被選擇： 0 + 7 + 9 + 13 + 19 = 48（我們失去3）

如果4選自：（7成爲3） 3 + 3 + 9 + 13 + 19 = 47（我們失去4）

如果選擇9：（9成爲7） 3 + 7 + 7 + 13 + 19 = 49（我們輸了2）

如果13選擇：我們失去13 - 如果選擇19 9 = 4

：我們失去19 - 13 = 6個

最低損失在這種情況下是：編號9（損耗= 2）。

我們刪除9，然後我們有K = 4。

對於第二數量，以除去，我們有4個選項：

如果我們除去3： 0 + 7 + 7 + 13 + 19 =＃（我們失去3）

如果我們除去7 （7-3）x 2 = 8）

如果我們刪除13： 3 + 7 + 3 + 3 + 13 + 19 = 7 + 7 + 19（損失= 13-7 = 6）

如果刪除了19： 3 + 7 + 7 + 13 + 13（損失= 6）這裏

最佳選擇是去除＃3 然後K = 3實現的總和：46

我不知道這是否是最佳的，你可以通過比較與蠻力多案件進行驗證。但是，即使這不是最佳的，也可以給出好的結果。