У меня есть алгоритм, который принимает два входа: набор из N элементов, которые будут добавлены к сумкам M.
Мой алгоритм генерирует все возможные присвоения элементов m сумкам. Например:
мы установили = {x1, x2, x3} и сумки = {b1, b2} Итак:
-итация 1: [b1 = {x1}, b2 = { empty}] и [b1 = {empty}, b2 = {x1}]
-итация 2: [b1 = {x1, x2}, b2 = {empty}], [b1 = {x1}, b2 = {x2}] и [b1 = {пусто}, b2 = {x1, x2}]
et c .......
Мой вопрос: как математически доказать, что мой алгоритм генерирует все возможные назначения?
Я пытался сделать это, используя алгебру множеств: я предполагал, что A содержит все возможные назначения, а B содержит A \ B ^ c, где B ^ c - это набор не сгенерированных распределений или дополнений B. Таким образом, чтобы получить A = B i, чтобы доказать, что:
A Δ B = emptyset => (A ∩ B ^ c) и ( B ^ A ^ c) = emptyset
A содержит все возможные назначения, тогда, A ^ c = emptyset => B ^ A ^ c = emptyset
, но я не может доказать, что A ∩ B ^ c = emptyset т.е. B ^ c = emptyset
Помогите пожалуйста.