C# 0-1 Zaino Problema con somma nota e numero di zeri nel set

Question

Ho una tabella 5x5 di valori da 0 a 3 compresi con tutti i valori sconosciuti. Conosco sia la somma dei valori che il numero di zeri per ogni riga e colonna. Come farei a risolvere questo problema dello zaino 0-1 usando C# e recuperando le possibili soluzioni che soddisfano le somme conosciute e il numero di zeri? I tavoli saranno sempre cinque righe e cinque colonne, quindi non è proprio uno zaino tradizionale.

Per esempio, dire che siamo in ingresso:

Row[0]: Sum=4, Zeros=1 
    [1]: Sum=5, Zeros=1 
    [2]: Sum=4, Zeros=2 
    [3]: Sum=8, Zeros=0 
    [4]: Sum=3, Zeros=2 

Col[0]: Sum=5, Zeros=1 
    [1]: Sum=3, Zeros=2 
    [2]: Sum=4, Zeros=2 
    [3]: Sum=5, Zeros=1 
    [4]: Sum=7, Zeros=0 

Vorremmo ottenere questo come una possibile soluzione:

[[ 0 1 1 1 1 ] 
[ 1 0 2 1 1 ] 
[ 2 1 0 0 1 ] 
[ 1 1 1 2 3 ] 
[ 1 0 0 1 1 ]] 

Che tipo di algoritmo dovrei impiegare in questa piuttosto strana situazione? Dovrei anche scrivere una classe solo per enumerare le permutazioni?

Modifica per chiarimenti: il problema non è che non posso enumerare le possibilità; è che non ho idea di come procedere per determinare in modo efficiente le permutazioni aggiungendo a una somma arbitraria pur contenendo il numero di zeri specificato e un massimo di 5 elementi.

Answer 1

Qui c'è il codice. Se hai bisogno di commenti non esitare a chiedere:

using System; 
using System.Diagnostics; 

namespace ConsoleApplication15 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      RowOrCol[] rows = new RowOrCol[] { 
       new RowOrCol(4, 1), 
       new RowOrCol(5, 1), 
       new RowOrCol(4, 2), 
       new RowOrCol(8, 0), 
       new RowOrCol(3, 2), 
      }; 

      RowOrCol[] cols = new RowOrCol[] { 
       new RowOrCol(5, 1), 
       new RowOrCol(3, 2), 
       new RowOrCol(4, 2), 
       new RowOrCol(5, 1), 
       new RowOrCol(7, 0), 
      }; 

      int[,] table = new int[5, 5]; 

      Stopwatch sw = Stopwatch.StartNew(); 

      int solutions = Do(table, rows, cols, 0, 0); 

      sw.Stop(); 

      Console.WriteLine(); 
      Console.WriteLine("Found {0} solutions in {1}ms", solutions, sw.ElapsedMilliseconds); 
      Console.ReadKey(); 
     } 

     public static int Do(int[,] table, RowOrCol[] rows, RowOrCol[] cols, int row, int col) 
     { 
      int solutions = 0; 

      int oldValueRowSum = rows[row].Sum; 
      int oldValueRowZero = rows[row].Zeros; 
      int oldValueColSum = cols[col].Sum; 
      int oldValueColZero = cols[col].Zeros; 

      int nextCol = col + 1; 
      int nextRow; 
      bool last = false; 

      if (nextCol == cols.Length) 
      { 
       nextCol = 0; 

       nextRow = row + 1; 

       if (nextRow == rows.Length) 
       { 
        last = true; 
       } 
      } 
      else 
      { 
       nextRow = row; 
      } 

      int i; 

      for (i = 0; i <= 3; i++) 
      { 
       table[row, col] = i; 

       if (i == 0) 
       { 
        rows[row].Zeros--; 
        cols[col].Zeros--; 

        if (rows[row].Zeros < 0) 
        { 
         continue; 
        } 

        if (cols[col].Zeros < 0) 
        { 
         continue; 
        } 
       } 
       else 
       { 
        if (i == 1) 
        { 
         rows[row].Zeros++; 
         cols[col].Zeros++; 
        } 

        rows[row].Sum--; 
        cols[col].Sum--; 

        if (rows[row].Sum < 0) 
        { 
         break; 
        } 
        else if (cols[col].Sum < 0) 
        { 
         break; 
        } 
       } 

       if (col == cols.Length - 1) 
       { 
        if (rows[row].Sum != 0 || rows[row].Zeros != 0) 
        { 
         continue; 
        } 
       } 

       if (row == rows.Length - 1) 
       { 
        if (cols[col].Sum != 0 || cols[col].Zeros != 0) 
        { 
         continue; 
        } 
       } 

       if (!last) 
       { 
        solutions += Do(table, rows, cols, nextRow, nextCol); 
       } 
       else 
       { 
        solutions++; 

        Console.WriteLine("Found solution:"); 

        var sums = new int[cols.Length]; 
        var zeross = new int[cols.Length]; 

        for (int j = 0; j < rows.Length; j++) 
        { 
         int sum = 0; 
         int zeros = 0; 

         for (int k = 0; k < cols.Length; k++) 
         { 
          Console.Write("{0,2} ", table[j, k]); 

          if (table[j, k] == 0) 
          { 
           zeros++; 
           zeross[k]++; 
          } 
          else 
          { 
           sum += table[j, k]; 
           sums[k] += table[j, k]; 
          } 
         } 

         Console.WriteLine("| Sum {0,2} | Zeros {1}", sum, zeros); 

         Debug.Assert(sum == rows[j].OriginalSum); 
         Debug.Assert(zeros == rows[j].OriginalZeros); 
        } 

        Console.WriteLine("---------------"); 

        for (int j = 0; j < cols.Length; j++) 
        { 
         Console.Write("{0,2} ", sums[j]); 
         Debug.Assert(sums[j] == cols[j].OriginalSum); 
        } 

        Console.WriteLine(); 

        for (int j = 0; j < cols.Length; j++) 
        { 
         Console.Write("{0,2} ", zeross[j]); 
         Debug.Assert(zeross[j] == cols[j].OriginalZeros); 
        } 

        Console.WriteLine(); 
       } 
      } 

      // The for cycle was broken at 0. We have to "readjust" the zeros. 
      if (i == 0) 
      { 
       rows[row].Zeros++; 
       cols[col].Zeros++; 
      } 

      // The for cycle exited "normally". i is too much big because the true last cycle was at 3. 
      if (i == 4) 
      { 
       i = 3; 
      } 

      // We readjust the sums. 
      rows[row].Sum += i; 
      cols[col].Sum += i; 

      Debug.Assert(oldValueRowSum == rows[row].Sum); 
      Debug.Assert(oldValueRowZero == rows[row].Zeros); 
      Debug.Assert(oldValueColSum == cols[col].Sum); 
      Debug.Assert(oldValueColZero == cols[col].Zeros); 

      return solutions; 
     } 
    } 

    public class RowOrCol 
    { 
     public readonly int OriginalSum; 
     public readonly int OriginalZeros; 

     public int Sum; 
     public int Zeros; 

     public RowOrCol(int sum, int zeros) 
     { 
      this.Sum = this.OriginalSum = sum; 
      this.Zeros = this.OriginalZeros = zeros; 
     } 
    } 
} 

Answer 2

Quanto velocemente deve essere? Ho appena provato un ingenuo "prova praticamente tutto" con alcuni aborti anticipati ma meno di quanto sarebbe possibile, ed è stato piuttosto veloce (meno di un millisecondo). Essa ha dato la soluzione:

[[ 0 1 1 1 1 ] 
[ 1 0 1 1 2 ] 
[ 1 0 0 1 2 ] 
[ 2 1 2 2 1 ] 
[ 1 1 0 0 1 ]] 

Se questa è una soluzione accettabile per te, posso pubblicare il codice (o semplicemente discuterne, è abbastanza prolisso, ma l'idea di fondo è banale)

edit: è anche banalmente estendibile per enumerare tutte le soluzioni. Ne ha trovate 400 in 15 millisecondi e afferma che non ce ne sono più di così. È corretto?

---

Quello che ho fatto, ero partono da 0,0 e cercare tutti i valori che potrei riempire in quel luogo (0 se min (3, rowsum [0])), riempirlo esso (sottraendolo rowsum [y] e colsum [x] e sottraendone uno da rowzero [y] e colzero [x] se il valore era zero), quindi ricorsivamente per 0,1; 0,2; 0,3; poi a 0,4 ho un caso speciale in cui compilo solo il file rimanente se è non negativo (altrimenti, interrompo il tentativo corrente - cioè salgo nell'albero di ricorsione), e qualcosa di simile per quando y = 4. Nel frattempo, abortisco quando un columero di righeum colzero o rowzero diventa negativo.

La scheda corrente è una soluzione se e solo se tutti i restanti fileums colonneum di colzero e rowzero sono zero. Quindi mi limito a testarlo e aggiungerlo alle soluzioni, se lo è. Non avrà alcuna entrata negativa per costruzione.