平衡分区： . 您有一组 n 个整数，每个整数都在 0 ... K 范围内。将这些整数分成两个子集，使 |S1 - S2| 最小化，其中 S1 和 S2 表示两个子集中每个子集中元素的总和。背包问题：给定一组项目，每个项目都有一个重量和一个值，确定要包含在集合中的每个项目的数量，使得总重量小于或等于给定的限制，并且总值与可能的。不能两次使用同一个对象。
似乎平衡分区问题的解决方案是简单地应用背包算法，对于背包的大小 S/2，其中 S 是所有输入数字的总和，权重等于每个对象的值。不过，这里说背包问题是 O(nC)，而平衡分区问题是 O(n^2 k)。我错过了什么？