3-partition problem: Difference between revisions

Revision as of 12:03, 16 April 2022

Revision as of 12:12, 16 April 2022

Line 8:

==Example==

Example 1: The set ''S'' = { 20, 23, 25, 30, 49, 45, 27, 30, 30, 40, 22, 19 } can be partitioned into the four sets { 20, 25, 45 }, { 23, 27, 40 }, { 49, 22, 19 } , { 30, 30, 30}, each of which sumsums 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.

Example 12: The set ''S'' = {41,5,5,5 2, 5, 6}, thus m=27, and9} T=15. Therecan isbe partitioned feasibleinto 3-partitionthe two sets {41, 5,6 9}, {52,5 6,5 7} each of which sum to ''T'' = 15.

Example 3 (every integer in ''S'' is strictly between ''T''/4 and ''T''/2): ''S'' = {4,45,45,65,65,6}, thus ''m''=2, and ''T''=15. There is no feasible solution3-partition {4,5,6}, {5,5,5}.

Example 4 (every integer in ''S'' is strictly between ''T''/4 and ''T''/2): ''S'' = {4,4,4,6,6,6}, thus ''m''=2, and ''T''=15. There is no feasible solution.

==Strong NP-completeness==