1
$\begingroup$

I am doing a research about the load balancing problem in 5G system, but I am not sure if my problem is a NP-complete problem.

The problem is:

  • given a set of n items and a set of m knapsack
  • capacity of knapsacks are equal
  • the weight of item j in knapsack i is w[i][j],that means weight of a item in each knapsack are different
  • each profit of items are equal

I am not trying to put all item in least knapsack like bin packing problem. I saw some similar question answered, but no one is identical to this case. In this case, the goal is to put as more as possible item with m knapsacks. Is the problem a NP-complete problem?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This problem can be shown to be NP-complete via reduction from PARTITION. Simply take $m=2$, the weights of each item to be the same across both knapsacks, and the capacities of each knapsack to be half the total weight across all items.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you mean : in a special case, total weight of items are equal to total capacity, so if the goal is to put max number of item to the two pocket, it can reduce to the partition problem? $\endgroup$
    – Ken Chang
    May 24, 2019 at 3:30
  • $\begingroup$ Yes, the total capacity across the two knapsacks is equal to the total weight of all items. $\endgroup$
    – mhum
    May 24, 2019 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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