Partizionamento impostato in sottoinsiemi rispetto all'uguaglianza di somma tra sottoinsiemi

Come @wmeyer ha notato, questo problema può essere affermato in modo abbastanza carino usando la Programmazione Vincoli. E questa semplice istanza di problema è facilmente risolvibile.

Innanzitutto, ecco un modello di alto livello scritto in MiniZinc che è fondamentalmente questo codice, senza la sezione di uscita. (Vedi link per il modello completo.)

% problem instance and its length
array[1..n] of int: s = [3, 1, 1, 2, 2, 1, 5, 2, 7];
int: n = 9;

% number of subsets
int: num_subsets = 2;

% the decision variables
% to which subset does x[i] belong?
array[1..n] of var 1..num_subsets: x;

solve satisfy; % we want all solutions

% Constraints

% Ensure that the sum of the subsets are the same
constraint
   forall(p in 1..num_subsets-1) (
      sum([s[i]*bool2int(x[i] == p) | i in 1..n]) == 
      sum([s[i]*bool2int(x[i] == p+1) | i in 1..n])
   )
;

% symmetry breaking: assign the first number to subset 1
constraint x[1] = 1;

Poiché la domanda è taggata "C #", ecco il modello che utilizza l'interfaccia C # di Google o-tools (con un approccio leggermente diverso rispetto al modello MiniZinc): link

Nota: Per i numeri forniti - e usando la rottura della simmetria assegnando il primo numero al sottoinsieme 1 - ci sono 19 diverse partizioni (soluzioni) con 2 sottoinsiemi e 42 diverse partizioni quando si usano 3 sottoinsiemi. Per 4 sottoinsiemi non c'è soluzione.

Come qualcuno ha commentato, questo problema è isomorfo a "sottoinsieme somma", e quindi è NP-completo. Fondamentalmente, le soluzioni ingenue di questo problema sono le soluzioni migliori e sono molto, molto brutte. :) Lo dico solo per non cercare una versione più "ottimizzata" o qualcosa del genere.

using System;
using System.Linq;
public class CandidateCode
{
    public static string partition(int[] input1)
    {
        bool[] best_assignment = PartitionValues(input1);

        string result1 = "", result2 = "";
        int total1 = 0, total2 = 0;
        for (int i = 0; i < best_assignment.Length; i++)
        {
            if (best_assignment[i])
            {
                result1 += "\r\n " + input1[i];
                total1 += input1[i];
            }
            else
            {
                result2 += "\r\n " + input1[i];
                total2 += input1[i];
            }
        }
        if (result1.Length > 0) result1 = result1.Substring(2);
        if (result2.Length > 0) result2 = result2.Substring(2);

        return "{"+ result1 + " } {" + result2 + " } total  " + total1.ToString() + " & " + total2.ToString();
    }

    private static bool[] PartitionValues(int[] values)
    {
        bool[] best_assignment = new bool[values.Length];
        bool[] test_assignment = new bool[values.Length];

        int total_value = values.Sum();

        int best_err = total_value;
        PartitionValuesFromIndex(values, 0, total_value, test_assignment, 0, ref best_assignment, ref best_err);

        return best_assignment;
    }

    private static void PartitionValuesFromIndex(int[] values, int start_index, int total_value,
            bool[] test_assignment, int test_value,
            ref bool[] best_assignment, ref int best_err)
    {
        // If start_index is beyond the end of the array,
        // then all entries have been assigned.
        if (start_index >= values.Length)
        {
            // We're done. See if this assignment is better than what we have so far.
            int test_err = Math.Abs(2 * test_value - total_value);
            if (test_err < best_err)
            {
                // This is an improvement. Save it.
                best_err = test_err;
                best_assignment = (bool[])test_assignment.Clone();
            }
        }
        else
        {
            // Try adding values[start_index] to set 1.
            test_assignment[start_index] = true;
            PartitionValuesFromIndex(values, start_index + 1, total_value,
                test_assignment, test_value + values[start_index],
                ref best_assignment, ref best_err);

            // Try adding values[start_index] to set 2.
            test_assignment[start_index] = false;
            PartitionValuesFromIndex(values, start_index + 1, total_value,
                test_assignment, test_value,
                ref best_assignment, ref best_err);
        }
    }
}