算法整數

的總和

可能重複：
Finding all possible combinations of numbers to reach a given sum 算法整數

我要創建方法，其從數字陣列選擇數字，這和將是精確的所需的一個或如果這種不存在選擇最小的更大的一個。這個函數的算法是什麼？

public int[] selectExactSum(int[] X, int SUM) { 
}

例如：號碼爲：{5,2，8,4，6}和所需的總和爲12。

其結果將是：{2，4，6}

如果需要的總和是13，結果將是：{2，8，4} - 因此，總和在這種情況下是14 - 第一個最小的更大的一個。

如果所需總和爲15，則可能的結果是：{5,2,8}或{5,4,6}。在這種情況下，返回你的選擇之一 - 可能是你得到的第一個。

自定義數字和總和的算法是什麼？

感謝，西蒙

來源

2012-05-16 simonxy

你認爲@Simonxy的做法是什麼？你有什麼想法嗎？ – Yavar

作業？如果是，請添加一個標籤'homework' – Crazenezz

在sum = 12的例子中，有幾個解決方案（2,4,6,8,4）。應該找到他們？否則，這兩種解決方案是等價的還是一種比另一種更好？ –

這就是所謂subset sum問題的一般化情況。這是一個NP完全問題，因此最着名的算法是pseudo-polynomial。如果您瞭解上述鏈接算法，則可以扣除解決問題所需的修改。

來源

2012-05-16 07:53:35 kosii

你有一些例子嗎？謝謝。 – simonxy

如何遞歸呢？

public static int[] SelectExactSum(int[] x, int sum) { 
    int[] 
    rest = x.Skip(1).ToArray(), 
    with = x.Length == 1 ? x : x.Take(1).Concat(SelectExactSum(rest, sum - x[0])).ToArray(), 
    without = x.Length == 1 ? new int[0] : SelectExactSum(rest, sum); 
    int withSum = with.Sum(), withoutSum = without.Sum(); 
    return 
    withSum >= sum ? (withoutSum >= sum ? (withSum < withoutSum ? with : without) : with) : 
    withoutSum >= sum ? without : new int[0]; 
}

注：調用SelectExactSum(new int[] {5,2,8,4,6}, 13)不返回{2,8,4}如問題所說，但{5,8}作爲實際總計爲13

來源

2012-05-16 08:09:51 Guffa

通過這種方式可以殺死內存：'int [] rest = ...，with = ...，without = ...'和遞歸調用。 –

@SaeedAmiri：行爲在記憶之前成爲問題looooong。對於有20個值的數組，最大內存使用量約爲2 kb。 – Guffa

我花了大約15分鐘做它，你可以看到它運行在這裏：

http://jesuso.net/projects/selectExactSum/index.php?numbers=5%2C2%2C8%2C4%2C6&reqSum=15

而這裏的代碼：

http://jesuso.net/projects/selectExactSum/selectExactSum.txt

我使它儘可能簡單，但是它在PHP上製作，讓我知道如果您需要一些幫助將它轉換爲C＃。

來源

2012-05-16 08:21:41

注意*：只是爲了讓你採取多種方式之一來做到這一點，當然有更好的方式來解決這個問題，你仍然必須添加錯誤處理和類似的東西，但我有點喜歡測試它在最後你可以使用像這樣的東西：http://jesuso.net/projects/selectExactSum/index.php?numbers=5%2C2%2C8%2C4%2C6&reqSum=105它仍然有效：D 所以，你只要你有1對和1個奇數，或者給定的數字只有1，就可以和任何數字相加。 –

您可以在ideone.com上發佈您的代碼 –

當我閱讀您的代碼（我不是php）時，我不確定它是否正常工作。你能用JavaScript或C＃解釋嗎？ – simonxy

回答

相關問題