Изменения

Перейти к: навигация, поиск

NP-полнота задачи о сумме подмножества

18 байт добавлено, 20:23, 17 мая 2016
м
big union symbols
*<math>s = 111144</math>
<math>S = (\cup_bigcup\limits_{i=1 \ldots }^{4} v_{i}) \cup (\cup_bigcup\limits_{i=1 \ldots }^{4} w_{i}) \cup (\cup_bigcup\limits_{i=1 \ldots }^{2} d_{i}) \cup (\cup_bigcup\limits_{i=1 \ldots }^{2} e_{i})</math>
Тогда набору значений <math>Y = (0,0,0,1):~ \phi(Y) = 1</math> соответствует <math>S' = \{w_{1},~w_{2},~w_{3},~v_{4},~d_{1},~e_{1},~e_{2}\}</math>. И действительно, <math>100001 + 10000 + 1010 + 101 + 10 + 20 + 2 = 111144</math>.
54
правки

Навигация