Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed

Problem Detail: 

How to think about dynamic algorithms which allows negative integers in input (where it's problematic, because obviously it's not always the case)?

Examples:

• Partition Problem with negative numbers in set allowed
• Knapsack problem with negative weights are allowed

Is there some general idea to handle these or other similar dynamic algorithms?

Asked By : Świstak35

Answered By : Yuval Filmus

In the two examples you mention, the dynamic programming algorithms work just as well. Let's take partition as an example. The dynamic programming approach computes, for every $m$, the sums of all subsets of $\{w_1,\ldots,w_m\}$. This works just as well if negative numbers are allowed. The range of the table has to be modified accordingly, to account fo the largest possible positive and negative amounts. With knapsack it's similar, and I'll let you work out the details.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23740