3
$\begingroup$

Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.

The total value of $n$ gifts is $W$. The most fair division will be to give all of them gifts of the total value $W/3$.

Suppose $W_1, W_2, W_3$ are the total values of the gifts of the first, second and third person.

We want to minimize: $\max(W_1, W_2, W_3) - \min(W_1, W_2, W_3)$.

Using the knapsack problem. Assign to the first knapsack the "weight" $W/3$ and the same for the second knapsack $W/3$. Use double knapsack algorithm and get the for each knapsack the gifts that maximizes the total value but obeys the $W_{i \in {1,2}} \le W/3$ property. Then the remaining gifts give to the third person.

The question is if such kind of algorithm is correct? If so why? If no can you provide your own solution to the problem?

$\endgroup$
  • $\begingroup$ Let say you have only three gifts with weights 1,1,10 with $W=12$. Knapsack's output is nothing, but $w_1=10, w_2=1, w_3=1$ is actually a valid answer. $\endgroup$ – aminrd Sep 30 at 18:21
  • $\begingroup$ @aminrd But, does it contradict to the given algorithm? I would take two persons with the constraint that their knapsack must have at most weight 3. Chose gifts for them. And then the remaining will go the the other person (“third”). $\endgroup$ – user13 Sep 30 at 18:25
  • 1
    $\begingroup$ You are right, I found a better example. Let say you have $w = {3,3,3,3,3}$ with $W=15$ and $ \frac{W}{3}=5 $. So, Knapsack assigns $w_1=3, w_2 = 3$ and the rest is $w_3=9$. However, the best assignment is $w_1=3, w_2=6, w_3=6$. $\endgroup$ – aminrd Sep 30 at 18:29
  • $\begingroup$ @aminrd Yes, thank you! Do you have any thoughts on how to solve this? $\endgroup$ – user13 Sep 30 at 18:33
  • 1
    $\begingroup$ The problem changes completely if each gift has a different value to each receiver. And in this case you might find a solution that is absolutely "fair" by giving each person the same value, but a different solution might give everyone more value, but not in a fair way. $\endgroup$ – gnasher729 Sep 30 at 23:38
-1
$\begingroup$

What if having empty basket for each person, keep tracking on sum of items in each basket. So we always know which basket has the minimum value. Then we can go over list of items and put the new one, in the basket with minimum total value. The complexity of this hypothesis is $O(n \log(n))$.

$\endgroup$
  • $\begingroup$ There is no reason to believe this gets anywhere close to an optimal answer. $\endgroup$ – gnasher729 Oct 5 at 7:35
  • $\begingroup$ What about this case [1, 2, 3, 4, 5, 6] This algorithm assigns: {1, 4}, {2, 5} and {3, 6} with final values 1+4=5, 2+5=7, 3+6=9 and difference of max and min is 9-5=4 but the optimal answer is 1+6=7, 2+5=7, 3+4=7 with difference of max and min 7-7=0. $\endgroup$ – Marcelo Fornet Oct 7 at 3:42
  • $\begingroup$ You are right. That was just a hypothesis. I don't know how to remove this answer! $\endgroup$ – aminrd Oct 7 at 16:20
1
$\begingroup$

Say your best answer so far has a difference D, and you can give w/3 - a to the first person. The best result you can have is w/3 + a/2 to the other two, giving a difference of 3a/2, so you only proceed if 3a < 2D (actually, you will distinguish cases depending on w modulo 3 if all sizes are integers).

Then you pick items for the second person. If you can give them w/3 - b, b ≥ a, then diff = a + 2b, so you need a + 2b < D, or b < (D - a) / 2; only if a ≤ D/3. If you can give them w/3 - b, 0 ≤ b ≤ a, then diff = 2a + b, so you need b ≤ D - 2a, only if a ≤ D/2. You analyse the case w/3 + b for the second person as well, so you find a range for how much goes to the second person.

Problem is that you waste a lot of time with sets for the first person that are not particularly close to w/3. Based on the number of items and their values I'd make an estimate how good the best solution would be (how much the smallest D will be) and only look for items for the first person that might give a result < 2D, then extending to 4D, 8D etc. if nothing is found.

And you should check the case where one item is > w/3 first, or you might waste a lot of time.

$\endgroup$
1
$\begingroup$

Problem 1: Divide $𝑛$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people.

Problem 2: Partition problem

Problem 2 is known to be NP-complete. Given an instance $A$ of problem 2, we can transform it into an instance $B$ of problem 1. Here is the rule of transformation: $A= w_1, w_2, \dots, w_n$. Let $t= \sum_{i=1}^n w_i$. Now $B=\frac{t}{2}, w_1, w_2, \dots, w_n$.

Then it is easy to prove that $A$ has a partition if and only if $B$ has zero solution. Hence problem 1 is NP-hard.

$\endgroup$
1
$\begingroup$

This problem can be solved using double knapsack algorithm, just don't restrict yourself to the case $W_{i \in {1, 2}} \le \frac{W}{3}$. Find all ways to decompose elements in subsets of value $A$ and $B$. Define $C = W - A - B$ (the value of the remaining set) and let the value of such decomposition be $max(A, B, C) - min(A, B, C)$. You just need to find the decomposition with least value. This can be solved in $O(W^2 \cdot n)$ (This is a pseudo-polynomial solution to the problem).

The problem is NP-Hard as mentioned previously by @jaxxa, and can be solved in $O(3^n)$ by trying all possible decomposition in three different sets, and finding the value of each decomposition.

There exists a faster solution using Meet in the middle in $O(3^{\frac{n}{2}} poly(n))$. Roughly speaking this is done dividing the set in two "equals" sets left and right, finding all decomposition in three sets of both left and right, and finding fast for every decomposition in one side best decomposition in the other side. This last part is obviously under-explained, but if someone is interested I can elaborate more on how this algorithm works.

By the way, I met this problem participating in competitive programming contests, and you can find it here. The statement is in spanish, but it is basically asking the exact same question.

$\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.