バランスの取れたパーティション：。それぞれ0...Kの範囲のn個の整数のセットがあります。|S1-S2|を最小化するように、これらの整数を2つのサブセットに分割します。ここで、S1とS2は、2つのサブセットのそれぞれの要素の合計を示します。ナップサック問題：それぞれに重みと値があるアイテムのセットが与えられた場合、コレクションに含める各アイテムの数を決定して、合計の重みが指定された制限以下になり、合計値が可能。同じオブジェクトを2回使用することはできません。
バランスの取れたパーティションの問題の解決策は、ナップサックS / 2のサイズにナップサックアルゴリズムを適用することであるようです。ここで、Sはすべての入力数値の合計であり、重みは各オブジェクトの値に等しくなります。それでも、ここでは、ナップサック問題はO（nC）であり、平衡分割問題はO（n ^ 2 k）であると述べています。私は何が欠けていますか？