algorithm - Algorithmic classification -


i'm trying classify following problem:

i have n empty boxes (ni volume of i-th box, 1 <= <= n) , m divisible items (mj volume of j-th item j, 1 <= j <= m). total volume of boxes equal total volume of items. need find distribution of items among boxes minimizes number of item divisions.

i suppose problem np-complete, , kind of set coverage problem, can't find appropriate variation of it.

the special case n=2 , n_1 = n_2 subset sum problem

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

since optimum value of problem formulated above 0 if , if instance (viewed instance of subset sum) has solution. hence, presented problem indeed np-hard.


Comments