邏輯形式獲得最低UPPERBOUND對於給定數目從一組數字

Question

的

我的問題如下 -

我有一些數字和我一樣，如下─

2 
    2 
    2 
    2 
    3 
    3 
17 
17 
17 
17 
17 
17 
17 
17 
17 
34 
34 
34 
34 
34 
68 
68 
68 
136 

所以，如果我給出以下作爲輸入數，輸出應該是如下 -

[輸出是給定數目的總和， 剛剛大於輸入]

Input Output 
    3  2,2 
    4  2,2 
    254 17,34,68,136 
    7  2,3,3 [or also with 2,2,2,2 but if return same sum, 
        then number count should min] 
    205 2,68,136 
    10  2,2,3,3 

我不只是想嘗試每一個組合（即蠻力）來獲得結果。所以想問一下上面的情況是否有可能的有效算法。

謝謝。

Answer 1

我發現了一個可能的起點on Wikipedia：

更一般的問題要求一個子集的總和爲規定值（不一定是0）。它可以通過上述算法的簡單修改來解決。對於每個xi都是正數並且以相同常數爲界的情況，Pisinger發現了一個線性時間算法[3]。

您的基本問題看起來像是一個擴展版本。你需要找到您所設定的總和爲input的一個子集 - 或做不到這一點，總和爲input+1，或做不到這一點，總和爲input+2等

所以只需運行Pisinger算法反覆，隨着目標的款項，直到你結果呢？ （我沒看過這篇論文，所以我不知道Pisinger算法是否滿足選擇最小子集的tiebreaker條件。）