算法分类

Question

我正在尝试对以下问题进行分类：

我有N个空框（N_I是第I个框的体积，1<=I<=N）和M个可分割项（M_j为第j个项j的体积，1\lt；=j<=M）。所有箱子的总体积恰好等于所有物品的总体积。我需要找到一个在盒子之间的项目分布，最大限度地减少项目划分的数量。

我认为这个问题是NP完全的，是某种集合覆盖问题，但我找不到它的适当变体。

Answer 1

特殊情况N=2 and n_1 = n_2正是子集和问题

http://en.wikipedia.org/wiki/Subset_sum_problem

因为上面公式化的问题的最优值是0当且仅当该实例（被视为子集和的实例）具有解决方案。因此，所提出的问题确实是NP困难的。