Given below is a sample problem:
Given n numbers such that their sum is not divisible by 4, remove k numbers such that after every removal, the sum of remaining numbers is not divisible by 4. Find the maximal sum of n-k remaining numbers.
Solution:
Divide the initial n numbers into 4 separate arrays corresponding to the 4 different remainders they leave when divided by 4. Now, sort them. Lets call these arrays a0, a1, a2, a3. Now, if say the sum of n numbers is divisible by 4.
f(k, a0, a1, a2, a3) = max {f(k-1, a0, a1+1,a2,a3), f(k-1,a0,a1,a2+1,a3), f(k-1,a0,a1,a2,a3+1) }
If the sum upon dividing with 4 gives a remainder of 1, we would have considered the arrays a0, a2 and a3.
Test case: n = 10 {44, 12, 45, 23, 22, 34, 47, 37, 50, 31}, Sum = 345
Answers:
k = 1, 333
k = 2, 311
k = 3, 279
k = 4, 257
k = 5, 223
k = 6, 186
k = 7, 142
k = 8, 97
k = 9, 50
k = 10, 0