Search code examples
calgorithmdata-partitioning

C algorithm for Partition issues

Given a set of integers S:

How can the set be divided into k parts such that the sum of each part is minimal? Please give also a C implementation.

Example:

S = {1, 2, 3, 4, 5, 6} and k = 3

The partition

 S1 = {1, 6}
 S2 = {2, 5}
 S3 = {3, 4}

has the property that the sum of each partition is minimal.

Solution

  • This page describes the problem fairly well and even provides pseudocode for an algorithm:

    http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM