2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.