Subtotal problem

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

Problem Description

A set of whole numbers is given . We are looking for a subset, the element sum of which is at most, but not greater than a given upper bound (it is often asked to reach the bound exactly). ${\ displaystyle I = \ {w_ {1}, w_ {2}, \ dotsc, w_ {n} \}}$ ${\ displaystyle c}$ ${\ displaystyle c}$

Formal: We are looking for those who maximize under the secondary condition . ${\ displaystyle x_ {1}, \ dotsc, x_ {n} \ in \ {0,1 \}}$ ${\ displaystyle \ sum _ {j = 1} ^ {n} {w_ {j} x_ {j}}}$ ${\ displaystyle \ sum _ {j = 1} ^ {n} {w_ {j} x_ {j}} \ leq c}$

NP completeness

The problem is NP-complete and therefore presumably cannot be solved efficiently . It can be solved using the branch-and-bound method.

The proof of the NP severity is done by reducing 3-SAT . For a given set of clauses with the variables , the decimal numbers and the limit are constructed using a table. It is assumed that there are no clauses containing and at the same time; this is not a restriction, since such a clause would always be fulfilled and can therefore be omitted without changing the meaning. ${\ displaystyle C_ {1} \ wedge C_ {2} \ wedge \ ldots C_ {m}}$ ${\ displaystyle x_ {1} \ ldots x_ {n}}$ ${\ displaystyle w_ {1} \ ldots w_ {2n + 2m}}$ ${\ displaystyle c}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ overline {x_ {i}}}}$

For example, the formula is processed as follows (an explanation follows the table). ${\ displaystyle (x_ {1} \ vee {\ overline {x_ {2}}} \ vee x_ {3}) \ wedge (x_ {1} \ vee x_ {2} \ vee x_ {3}) \ wedge ( {\ overline {x_ {1}}} \ vee {\ overline {x_ {2}}} \ vee {\ overline {x_ {3}}})}$

	${\ displaystyle x_ {1}}$	${\ displaystyle x_ {2}}$	${\ displaystyle x_ {3}}$	${\ displaystyle C_ {1}}$	${\ displaystyle C_ {2}}$	${\ displaystyle C_ {3}}$
${\ displaystyle w_ {1}}$	1	0	0	1	1	0
${\ displaystyle w_ {2}}$	1	0	0	0	0	1
${\ displaystyle w_ {3}}$	0	1	0	0	1	0
${\ displaystyle w_ {4}}$	0	1	0	1	0	1
${\ displaystyle w_ {5}}$	0	0	1	1	1	0
${\ displaystyle w_ {6 = 2n}}$	0	0	1	0	0	1
${\ displaystyle w_ {7}}$	0	0	0	1	0	0
${\ displaystyle w_ {8}}$	0	0	0	2	0	0
${\ displaystyle w_ {9}}$	0	0	0	0	1	0
${\ displaystyle w_ {10}}$	0	0	0	0	2	0
${\ displaystyle w_ {11}}$	0	0	0	0	0	1
${\ displaystyle w_ {12 = 2n + 2m}}$	0	0	0	0	0	2
${\ displaystyle c}$	1	1	1	4th	4th	4th

The digits in a line are interpreted as digits of a decimal number.
The first 2n lines are just a coding of the formula itself: means that in the clauses and , but does not appear . implements this for , for , for etc. ${\ displaystyle w_ {1} = 100110}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle C_ {1}}$ ${\ displaystyle C_ {2}}$ ${\ displaystyle C_ {3}}$ ${\ displaystyle w_ {2}}$ ${\ displaystyle {\ overline {x_ {1}}}}$ ${\ displaystyle w_ {3}}$ ${\ displaystyle x_ {2}}$ ${\ displaystyle w_ {4}}$ ${\ displaystyle {\ overline {x_ {2}}}}$
Lines to are "correction lines" which only have the value 1 or 2 alternately on the diagonal. ${\ displaystyle w_ {2n + 1}}$ ${\ displaystyle w_ {2n + 2m}}$
The number consists only of n ones and m fours. This means that when the column values are added, only either or ; or etc. can be selected, which is set to true or false in the formula . The four are chosen in such a way that in addition to the two correction values, which together only result in 1 + 2 = 3, at least one of the variables must be present in the clauses in order to arrive at 4. Correction lines can be omitted if more variables are available. ${\ displaystyle c}$ ${\ displaystyle w_ {1}}$ ${\ displaystyle w_ {2}}$ ${\ displaystyle w_ {3}}$ ${\ displaystyle w_ {4}}$ ${\ displaystyle x_ {i}}$

If the Boolean formula now has a fulfilling assignment, we record the number if = true ; if = false the number . With that the ones in are correct. Since all clauses are fulfilled, there is at least one fulfilled variable in the numbers just added in each clause, so the column sums in the right part are already at least 1 and at most 3. Now you only have to choose the correcting variables appropriately to get to 4. With the constructed set it is possible to reach exactly if the formula can be fulfilled. ${\ displaystyle x_ {i}}$ ${\ displaystyle w_ {2i-1}}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle w_ {2i}}$ ${\ displaystyle c}$ ${\ displaystyle c}$

If it is now possible to achieve exactly, then the subset of must first have exactly one or ; or etc., because otherwise the ones in would not be fulfilled. This ensures that a variable is actually true or false (and not neither or both). With this selection of the subset, every clause must then also be fulfilled, because if no variable in a clause were fulfilled by the assignment, the addition would not result in the necessary four in . Therefore, the Boolean formula can be satisfied overall. ${\ displaystyle c}$ ${\ displaystyle w_ {i}}$ ${\ displaystyle w_ {1}}$ ${\ displaystyle w_ {2}}$ ${\ displaystyle w_ {3}}$ ${\ displaystyle w_ {4}}$ ${\ displaystyle c}$ ${\ displaystyle c}$

literature

Soma, Nei Y. Toth, Paolo: An exact algorithm for the subset sum problem. European Journal of Operational Research 136 pp. 57-66
Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein. Algorithms - An Introduction. , Oldenbourg-Verlag, 2004. ISBN 3-486-27515-1 . Pages 1017ff.