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

CC BY-SA 3.0
2013-07-11T18:18:37.890Z
2013-07-11T19:07:35.777Z
2013-07-11T19:07:35.777Z
Mohammad Al-Turkistany
<p>This looks like a variation of the <a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow">Knapsack problem</a>.</p>

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

<p>Here, you need to find a <a href="http://en.wikipedia.org/wiki/Partition_of_a_set" rel="nofollow">partition</a> of the items which minimizes a cost.</p>

<p><strong>EDIT</strong>: As someone mentionned on StackOverflow, this problem could be classified as a variation of the <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">Subset sum problem</a>. 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).</p>

CC BY-SA 3.0
2013-07-11T14:18:13.123Z
2013-07-11T14:47:04.947Z
2013-07-11T14:47:04.947Z
Vincent
<p>I'm trying to classify the following problem:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<ds.algorithms>
Algorithmic problem classification
roman-kashitsyn
# Algorithmic problem classification

(Asked by: username_0 on 2013-07-11)

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.

**Tags:** ds.algorithms

---

## 2 answers

### Answer by username_1 on 2013-07-11. Score: 2 | Accepted answer

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


---

### Answer by username_2 on 2013-07-11. Score: 0

This looks like a variation of the [Knapsack problem](https://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Partition_of_a_set) 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](http://en.wikipedia.org/wiki/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).


---

