嘗試所有排列

Question

對於我的程序，我試圖幫助用戶，並減少他或她的工作量。

有四個輸入數字。他們也可以應用不確定數量的數字。

例如，它們四個輸入號碼可以是{4,7,3,2}，並且它們可以施加到是數字{4,9,23}

結果應該是：4（輸入）被應用於4，使得集合看起來像：{0,7,3,2}然後7,2（輸入）被應用於9，使集合看起來像：{0,0,3,0}和{ 0,0,23}，並且因爲3或包括3的任何其他排列不匹配23,3仍然存在。

我該怎麼做？

Answer 1

你是說你想從輸入集中找到總和爲另一個集合中的值的項目？ 如果是這樣，那麼我相信這是Subset Sum Problem的一個實例，這是Knapsack Problem的特例。

子集合是NP-Complete。如果這些集合很大，那麼你將能夠做的最好的解決方案就是近似解決方案。