0
$\begingroup$

Candy Allocation Problem: Suppose there are $n$ candies, each with a weight $w_i$ gram. There are $m$ kids, and each kid needs to eat at least $\omega$ grams of candies to be full. Candies cannot be cut into pieces. Is there a candy allocation algorithm such that at least $k$ kids can be full?

Is the above problem NP-complete? It has some similarity to knapsack, but not exactly the same. Can someone help me?

$\endgroup$
  • $\begingroup$ What did you try? Did you get stuck somewhere? $\endgroup$ – Juho Dec 20 '16 at 11:48
  • $\begingroup$ I think bin-packing is the correct one. $\endgroup$ – Steve Yang Dec 20 '16 at 11:59
  • $\begingroup$ There is a trivial reduction from PARTITION. $\endgroup$ – Pontus Dec 21 '16 at 19:23
  • $\begingroup$ @Pontus Yes, you're right. I've seen that now. $\endgroup$ – Steve Yang Dec 22 '16 at 3:07
1
$\begingroup$

First, we prove that the decision version of the original problem is NP. Since an instance of an assignment can be verified within polynomial time, it's obviously NP.

Now, we try to prove the NP-hardness of the problem. Well, I believe this problem can be reduced from the bin-packing problem.

The bin-packing problem says the following: There are $n$ items each with a weight $w_i$ and $m$ bins. We want to put the items to bins. Each bin has a maximum weight limit $\omega$. The problem is to find a item assignment scheme so as to minimize the number of bins needed. Mathematically: $$\textrm{minimize}~~~ z = \sum_{j=1}^m y_j$$ Subject to: $$\sum_{i=1}^n w_i x_{i,j} \leq \omega y_j, \forall j \in \{1,2,\cdots,m\}$$ $$\sum_{j=1}^m x_{i,j} = 1, \forall i \in \{1,2,\cdots,n\}$$ $$y_j \in \{0,1\}, \forall j$$ $$x_{i,j} \in \{0,1\}, \forall i, \forall j$$ The problem is NP-hard, and its NP-hardness has already been proved. The decision version of this problem is NP-complete.

Note that in the candy allocation problem, we tend to maximize the number of kids that are completely full. Since the number of kids are the same, the problem is equivalent to minimizing the number of kids that are not full, while ensuring every candy is allocated. The problem is formalized as follow: $$\textrm{minimize}~~~ \sum_{j=1}^m y_j$$ Subject to: $$\sum_{i=1}^n x_{i,j}w_i \leq \omega y_j, \forall j \in \{1,\cdots,m\}$$ $$\sum_{j=1}^m x_{i,j}=1 ,\forall i \in \{1,\cdots,n\}$$ $$x_{i,j} \in \{0,1\}, \forall i, \forall j$$ $$y_j \in \{0,1\}, \forall j$$ where $y_j$ denotes if kid $j$ is hungry ("1" is hungry, "0" is full), and $x_{i,j}$ denotes if candy $i$ is allocated to kid $j$.

One can easily see that the problem is equivalently to the bin packing problem. Thus, candy allocation is NP-hard.

Since candy allocation is NP and NP-hard, it's NPC.

The definition of bin packing problem can also be found in https://en.wikipedia.org/wiki/Bin_packing_problem.

$\endgroup$
  • 1
    $\begingroup$ Bin packing requires positive weights but you use negative ones, so your reduction seems invalid. Note that changing from positive to negative weights can dramatically change the complexity of problems. For example, finding a minimum-weight path in a graph with positive weights is in P but doing so in a graph with negative weights is NP-hard (take an unweighted graph on $n$ vertices and set each weight to $-1$; now the min-weight path has length $1-n$ iff there is a Hamiltonian path). $\endgroup$ – David Richerby Dec 21 '16 at 15:54
  • $\begingroup$ @DavidRicherby We can see that in candy allocation problem, maximizing the number of kids that are full is equivalent to minimizing the number of kids that are still hungry, which is equivalent to bin-packing problem. $\endgroup$ – Steve Yang Dec 21 '16 at 16:09
  • $\begingroup$ This answer is incorrect. Why do you think that minimizing the number of kids who are not-full is equivalent to bin-packing? I don't see any equivalence proved here, merely a re-statement of the definition of bin-packing and a bald claim that they are the same problem. But they are not the same problem: bin-packing asks about placing all items into $k$ bins, so that no bin is overfull. Your problem asks about placing all candies into $k$ kids, so that every kid is completely full. Those aren't the same: bin-packing allows some bins to be less than completely full, whereas your problem doesn't. $\endgroup$ – D.W. Dec 21 '16 at 23:06
  • $\begingroup$ @D.W. I've rewrote the answer to make it obvious. $\endgroup$ – Steve Yang Dec 22 '16 at 3:06
  • $\begingroup$ $\sum_i x_{i,j} w_i \le \omega y_j$ is not the right constraint for the candy problem. The constraint you need to enforce is that if kid $j$ is hungry (i.e., if $y_j=1$), then $\sum_i x_{i,j} w_i < \omega$, and if kid $j$ is full (i.e., if $y_j=0$), then $\sum_i x_{i,j} w_i = \omega$ ... but that's not what the inequality you wrote actually does. In other words, your integer linear programming formulation for the candy problem is incorrect. $\endgroup$ – D.W. Dec 22 '16 at 16:39

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.