[Solved]: Solving a Variation of knapsack

Problem Detail: 

I'm working on a problem which to me, seems very similar to a knapsack problem:

A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store and bought $2k$ items: $f_1, f_2, ...f_{2k-1}, f_{2k}$. The items are priced: $p_1, p_2,...p_{2k-1}, p_{2k}$ respectively.

Help David arrange the items in pairs such that the price of the $2k$ items is minimal.

Suggest an algorithm which solves the problem in $O(klogk)$. Prove correctness and running time.

So this seems very similar to the knapsack problem, but I have not been able to find a good solution.

Any help will be appreciated. Thank you!

Asked By : user475680

Answered By : Yuval Filmus

I'll do the cases $k = 1$ and $k = 2$ for you. First, $k = 1$. Suppose there were two items, $f_1,f_2$, priced $p_1,p_2$. Without loss of generality, assume that $p_1 > p_2$. Then whatever you do, you will pay $f_1$.

When $k = 2$, there are four items $f_1,f_2,f_3,f_4$ and four prices $p_1,p_2,p_3,p_4$. Suppose again that $p_1>p_2>p_3>p_4$. There are three possible ways of pairing items: $(f_1,f_2),(f_3,f_4)$, $(f_1,f_3),(f_2,f_4)$, $(f_1,f_4),(f_2,f_3)$. You will pay $f_1+f_3,f_1+f_2,f_1+f_2$, respectively. The lowest number here is the first $f_1+f_3$ (why?). So you should choose the pairing $(f_1,f_2),(f_3,f_4)$.

The general case is very similar. Try to figure out what step takes time $O(k\log k)$ (I have hidden this step in the description above), and then what is the best pairing. Try to solve it on your own.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32839

3.2K people like this

 Download Related Notes/Documents