# Algorithmic problem classification

I'm trying to classify the following problem:

I have $N$ empty boxes ($n_i$ is the volume of the $i$-th box, $1 \leq i \leq N$) and $M$ divisible items ($m_j$ is the volume of $j$-th item, $1 \leq j \leq M$). The total volume of all boxes is exactly equal to the total volume of all items. I need to find a distribution of items among boxes which minimizes the number of item divisions.

I suppose this problem is NP-complete, and is some kind of set coverage problem, but I can't find appropriate variation of it.

## 2 Answers

The decision version of your problem is NP-complete. The NP-complete 3-Partition problem is reducible to your problem (input has only three boxes having the same volume with zero divisions of items).

This looks like a variation of the Knapsack problem.

In the original Knapsack problem, you need to find a subset of the items to maximize a profit.

Here, you need to find a partition of the items which minimizes a cost.

EDIT: As someone mentionned on StackOverflow, this problem could be classified as a variation of the Subset sum problem. However, your problem is an optimization problem: you also need to find the minimum cost yourself (which is a number between 0 and N-1).