Addiction

Problem statement

There are N addictions each has a strength S_i. At each week, you can remove one addiction and restore any number of addictions that you have removed. The only constrain is the change of total strength of addictions you currently have must falls into the range [-D, 0]. Find the maximum number of addictions that you can remove, and minimize the number of weeks to achieve this.

1 ≤ N ≤ 1000
1 ≤ S_i ≤ 10000

Solution
First, there is an interesting property that if an addiction can be removed, any addiction with less strength can be removed also.

Although this seem intuitive but we should prove it anyway. We prove it by induction.

Assume that we can remove some addiction with strength P. Consider an addiction with strength T (T < P). Let the set S be the set of addiction with strength smaller than T and Sum(S) be the sum of strength in S. If T-D <= Sum(S) <= T, then we are done. Else, we have Sum(S) > T. Consider the addiction with smallest strength Q in S, if Q is smaller or equal than D, then we remove it from S directly. Else, there must exist some combinations of addictions with strength smaller than Q with sum of strength in [Q-D,Q]. Then we can remove that addiction with strength Q and replace it with that combination. As a result, Sum(S) decrease not more that D in each step and it will fall into [T-D,T] eventually.

Actually this fact is not necessary for our solution, but it is beautiful :P.
The solution is simple - Dynamic Programming.

Sort the addiction by strength first. Assume F(i) be the minimum number of weeks to remove addiction i. We have

F(i) = F(x₁) + F(x₂) + ... + F(x_m)

where S_x1 + S_x2 + ... + S_xm is in the range [S_i-D, S_i].

And we can do this by a knapsack.
The total time complexity is O(N * max(S))