平衡分區vs揹包1/0複雜度

Question

平衡分區：。您有一組n個整數，每個整數在0 ... K範圍內。將這些整數分成兩個子集，這樣可以最小化| S1 - S2 |，其中S1和S2表示兩個子集中每個元素的總和。 揹包問題：給定一組物品，每個物品都有一個重量和一個值，確定要包括在一個集合中的每個物品的數量，以便總重量小於或等於給定的限制，並且總值是一樣大盡可能。不能使用同一個對象兩次。

似乎解決平衡分區問題的方法是簡單地將揹包算法應用於揹包S/2的大小，其中S是所有輸入數的總和，並且權重等於每個對象。不過，它表示here揹包問題是O（nC），而平衡分區問題是O（n^2 k）。我錯過了什麼？

Answer 1

因爲如果每個整數等於k，C可以等於k * n。所以你在這種情況下得到整數揹包問題O（k * n^2）的運行時間。