algorithm - サブセット選択

Question

次の選択問題があります: N 個のアイテムの母集団が与えられ、各アイテムは +ve コスト (C_i) を持ち、ユーザー入力 k と総コスト S が与えられます。N 個のアイテムの母集団から abs( S-sum(C_i)) は最小です。

これに関する助けに感謝します

Answer 1

N または S に境界がありますか? N が小さい場合は、すべてのサブセットを試すことができます。S が小さい場合は、knapsack で解決できます (min sum(C_i)>=​​S および max sum(C_i)<=S を探します)。