Subset sum problem

The partial sum problem (even subset sum problem, Eng. Subset sum problem) is a famous problem of computer science and operations research. It is a particular problem backpack.

SYMPTOMS

Given a set of integers. Wanted is a subset whose sum maximum element, but not greater than a given upper bound is ( often also asked the barrier to achieve exactly ).

Formal: Wanted are to maximize subject to the constraint.

NP- completeness

The problem is NP-complete and thus is unlikely to be solved efficiently. It can be solved by Branch and Bound methods.

The proof of NP-hardness is carried out by a reduction from 3-SAT. For a given set of clauses with the variables decimal numbers as well as the barrier be constructed using a table. It is assumed that there are no clauses, which contain and at the same time; this is not a limitation, since such a clause would be always satisfied and thus can be omitted without changing the meaning.

For example, the formula is processed ( an explanation follows the table) as follows.

• The first 2n rows are only an encoding of the formula itself: states that does not occur in the clauses and but. sets the order for, for, for, etc.
• The lines are to " correction lines ", each have alternately the value 1 or 2, only on the diagonal.
• The number consists only of n ones and m fours. This causes in addition to the column values ​​in the first n digits only either or; can be selected or etc., which is set in the formula to true or false. The fours are chosen so that in addition to the two correction values ​​together only 1 2 = 3 result, at least one of the variables in the clauses must be present to get to 4. If there are more variables available, correction lines may be omitted accordingly.

Now owns the Boolean formula is a satisfying assignment, so we take if = true on the number; = false if the number. This means that even the ones in correctly. Since all clauses are satisfied, at least one filled variable is in the just added numbers in each clause exists, thus the column sums are in the right part already at least 1 and at most 3 Now you have to choose only the correction variables suitable to get to 4. With the constructed set, it is possible to achieve accurate if the formula is satisfiable.

Now, if can be achieved exactly, so must the subset of initially exactly one or; or contain etc., otherwise in the ones were not met. This ensures that a variable actually true or false (and not none or both). This selection of the subset then every clause must be satisfied, because if no variable in a clause would be satisfied by the assignment, so the addition would not provide the necessary four- in. Therefore, the boolean formula is satisfiable in total.