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