3-partition problem: Difference between revisions

Revision as of 22:02, 18 November 2020

Revision as of 18:48, 7 December 2020

Line 8:

==Example==

The set ''S'' = { 20, 23, 25, 30, 49, 45, 27, 30, 30, 40, 22, 19 } can be partitioned into the threefour sets { 20, 25, 45 }, { 23, 27, 40 }, { 49, 22, 19 } , { 30, 30, 30}, each of which sum to ''T'' = 90. Another example; the set ''S'' = {1, 2, 5, 6, 7, 9} can be partitioned into the two sets {1, 5, 9}, {2, 6, 7} each of which sum to ''T'' = 15.

Another example;

The set ''S'' = {1, 2, 3, 4, 5, 6, 7, 8, 9} can be partitioned into the three sets {1, 5, 9}, {3, 4, 8}, {2, 6, 7} each of which sum to ''T'' = 15.

==Strong NP-completeness==