Search code examples
algorithmdynamic-programmingknapsack-problempartition-problem

Sum or difference of numbers in a set greater or equal to a number

I have a problem that states the following:

Given a sequence of numbers (S), an initial value (V) and a target value (T), check if there is a sequence of + and - operations that can be assigned to the sequence S (the operations must respect the sequence order) to reach a number greater than or equal to T, starting from V. Also, there is a limit X that cannot be broken at anytime (if the sum exits the interval [0, X] at anytime, that solution path is invalid. All the numbers in the problem are also inside this interval).

Also, I must find the biggest sum that can be obtained from those operations, respecting the limit rules (it can be broken if the -last- operation puts the total sum out of the limit).

I've been looking into it and researched a little about the dynamic programming solutions to the knapsack problem and the partition problem, and I believe the solution would be something in this line.

However I can't figure out how to deal with the limit rule and how I would be able to find the biggest sum. The limit problem arises in some situations: Suppose I try to find a knapsack solution to find the numbers that would be added and the rest of the numbers would be subtracted. The knapsack solution could break the upper limit on the sum, but it is possible that the actual sum wouldn't because of the order of the operations (it could subtract something before the limit is actually broken, then it wouldn't be broken at all).

Can anyone please help me find me find a good approach for this? Thank you.

Solution

  • This problem is a variation of the Partition Problem, where one set is the elements you add, and the other is the elements you substract.

    A possible solution is unsurprisingly based on the pseudo-polynomial solution of partition problem:

    D(V,0) = true
D(s,0) = false     s != V
D(s,i) = false    s<0 or s > X
D(s,i) = D(s-arr[i],i-1) OR D(s+arr[i],i-1)

    You can calculate the recursive relation efficiently and build your DP table of size (X+1)*(n+1).
    When you are done, you are looking for the largest value T<=s<=X in the table such that D(s,n) == true