Divide $n$ 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

cs.stackexchange https://cs.stackexchange.com/questions/115284

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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top