Monday, June 23, 2014

a bit of codechef: (June Cook-Off 2014) Knapsack Problem

Problem Statement:
(June Cook-Off 2014) Knapsack Problem

Summary:
Given $$3\leq N \geq 100000$$ items with weights $$1\leq w_i \leq 2$$ and costs $$1\leq c_i \leq 10^9$$, output maximum costs of each $$M$$ from 1 to total sum of all weights.

Solution:
At first it seems like the problem can be solved by normal Knapsack DP problems, with the recursion $$S(w) = \max_{w_i \in W} \{S(w-w_i) + c_i\}$$, but $$N$$ and hence $$M$$ is too big for this to finish quickly enough. There are also only 2 value for weights. This suggests a more specialized algorithm to output all costs in the most efficient manner.

For me this is a very interesting problem, and the following observation is the key to solving it:
1. Given $$M$$, we can try all $$m$$ and $$n$$ such that $$2m+n \leq M$$. Furthermore, given $$m$$ and $$n$$,  the maximum cost would be to choose $$m$$ items of biggest cost with weight equals to 2, and $$n$$ items of biggest cost with weight 1. Now we only need a way to choose combination of $$m$$ and $$n$$ effectively, and therefore the second observation:
2. Given $$m,n$$ which optimizes the cost when the total weight is $$M$$, we can find $$m',n'$$ of $$M+1$$ by taking the maximum of either $$m+1,n$$ or $$m,n+1$$ (we also have to ensure that the resulting $$m'$$ and $$n'$$ does not exceed the total 2s and 1s, or else maximum cost of $$M+1$$ is equal to $$M$$

The two observations above are enough for us to develop a bottom-up DP by storing the combination of $$m,n$$ for each $$M$$.