平衡分区：。您有一组 n 个整数，每个整数在 0 ...K. 将这些整数划分为两个子集，以便最小化 |S1 - S2|，其中 S1 和 S2 表示两个子集中每个元素的总和。背包问题：给定一组项目，每个项目都有一个重量和一个值，确定要包含在集合中的每个项目的数量，以便总重量小于或等于给定的限制，并且总值尽可能大。不能将同一对象使用两次。
似乎平衡分区问题的解决方案是简单地应用背包算法，对于背包 S/2 的大小，其中 S 是所有输入数字的总和，权重等于每个对象的值。尽管如此，它在这里说背包问题是O（nC），而平衡分区问题是O（n^2 k）。我错过了什么？
因为如果每个整数都等于k，C可以等于k*n。因此，在这种情况下，对于整数背包问题，您可以获得 O（k * n^2） 的运行时间。