我正在尝试对以下问题进行分类：
我有 N 个空盒子（n i是第 i 个盒子的体积，1 <= i <= N）和 M 个可分割项目（m j是第 j 个项目 j 的体积，1 <= j <= M ）。所有箱子的总体积正好等于所有物品的总体积。我需要找到盒子之间的项目分布，以最大限度地减少项目划分的数量。
我想这个问题是 NP 完全的，并且是某种集合覆盖问题，但我找不到它的适当变体。
问问题
103 次
1 回答
2
特殊情况N=2 and n_1 = n_2正是子集和问题
http://en.wikipedia.org/wiki/Subset_sum_problem
因为当且仅当实例（被视为子集和的实例）有解决方案时，上述问题的最优值是 0。因此，提出的问题确实是 NP 难的。
于 2013-07-11T14:17:01.833 回答