C# 0-1 Knapsack Problema con suma conocida y número de ceros en el conjunto

Question

Tengo una tabla de valores de 5x5 de 0 a 3 inclusive, con todos los valores desconocidos. Sé tanto la suma de los valores como el número de ceros para cada fila y columna. ¿Cómo voy a resolver este problema de mochila 0-1 usando C# y recuperando las posibles soluciones que satisfacen las sumas conocidas y el número de ceros? Las tablas siempre serán de cinco filas y cinco columnas, por lo que no es una mochila tradicional.

Por ejemplo, digamos que de entrada:

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 

Nos conseguir esto como una posible solución:

[[ 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 ]] 

Qué tipo de algoritmo debo emplear en este lugar extraño situación? ¿También tendría que escribir una clase solo para enumerar las permutaciones?

Editar para aclaración: el problema no es que no puedo enumerar las posibilidades; es que no tengo ni idea de cómo proceder para determinar de manera eficiente las permutaciones que se suman a una suma arbitraria mientras que contiene el número especificado de ceros y un máximo de 5 elementos.

Answer 1

Aquí está el código. Si necesita algún comentario, no dude en preguntar:

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

¿Qué tan rápido tiene que ser? Acabo de probar un ingenuo "probar casi cualquier cosa" con algunos abortos anticipados, pero menos de lo que sería posible, y fue bastante rápido (menos de un milisegundo). Se dio la solución:

[[ 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 ]] 

Si eso es una solución aceptable para usted, me pueden enviar el código (o simplemente para analizar el caso, es bastante detallado, pero la idea subyacente es trivial)

edición: es también trivialmente extensible a la enumeración de todas las soluciones. Encontró 400 de ellos en 15 milisegundos, y afirma que no hay más que eso. ¿Es eso correcto?

---

Lo que hice, era empezar en 0,0 y tratar todos los valores que podía llenar en ese lugar (0 pesar min (3, rowsum [0])), que se llenan (restarlo de rowsum [y] y colsum [x] y restando uno de rowzero [y] y colzero [x] si el valor era cero), entonces recursivamente haga esto para 0,1; 0,2; 0,3; luego, a 0,4 tengo un caso especial en el que simplemente llené el rowsum restante si no es negativo (de lo contrario, abortar el intento actual - es decir, subir en el árbol de recursión), y algo similar para cuando y = 4. Mientras tanto, aborto cuando cualquier rowsum colsum colzero o rowzero se vuelve negativo.

La placa actual es una solución si y solo si todos los rowsums columnums colzero's y rowzero's son cero. Así que solo pruebo para eso y lo agrego a las soluciones si es uno. No tendrá entradas negativas por construcción.