C# 0-1 Sırt Çantası Sorunun bilinen toplam sayısı ve sıfır sayısı ile sayısı

Question

Bilinmeyen tüm değerlerle birlikte 0 ile 3 arasında bir 5x5 değer tablosu var. Her bir satır ve sütun için değerlerin toplamını ve sıfır sayısını biliyorum. C# kullanarak bu 0-1 sırt çantası sorununu çözmek ve bilinen toplamları ve sıfır sayısını karşılayan olası çözümleri almak için nasıl giderim? Tablolar her zaman beş satır ve beş sütun olacak, bu yüzden geleneksel bir sırt çantası değil.

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 

Biz olası bir çözüm olarak bu alacağı: Örneğin

, biz girdi demek

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

Bu oldukça garip bir durumda algoritmanın ne tür istihdam gerekir? Permütasyonları sıralamak için bir sınıf yazmak zorunda mıyım? açıklama için

Düzenleme: Sorun olanaklarını numaralandırmak edemez değildir; Belirtilen sayıda sıfır ve en fazla 5 öğeyi içeren bir toplamı ekleyerek permütasyonları etkin bir şekilde belirleme konusunda nasıl gidileceğine dair bir fikrim yok.

Answer 1

Burada kod var. Herhangi bir yoruma ihtiyacınız varsa sormaya çekinmeyin:

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

Ne kadar hızlı olmak zorunda? Ben sadece bir naif "hemen hemen her şeyi deneyin" bazı erken iptaller ile ama mümkün olandan daha az, ve oldukça hızlı (bir milisaniyeden az) sınandı.

düzenlemek sizin için kabul edilebilir bir çözüm ise

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

, ben kod sonrası (ya da sadece tartışmak onu, oldukça ayrıntılı ama altta yatan fikir, önemsiz) olabilir: o da bu çözüm verdi Tüm çözümlerin numaralandırılması için önemsiz ölçüde uzatılabilir. Onlardan 400'ü 15 milisaniyede buldu ve bundan daha fazlası olmadığını iddia ediyor. Bu doğru mu?

---

Ne yaptıysam, 0,0 başlayacak ve ben o yerde doldurabilir misin tüm değerleri denemek oldu (0 dakika (3, rowsum [0]) gerçi), bunu doldurun (rowsum çıkarılmadan [y] ve colsum [x] ve bir tanesi sıfırdan fazzero [y] ve colzero [x] 'dan çıkarılırsa, bunu sırasıyla 0,1 için yapın; 0,2; 0,3; daha sonra 0,4'te, eğer negatif değilse diğer satırları dolduracağım özel bir durumum var (aksi halde, şu anki denemeyi iptal et - yani yineleme ağacında yukarı çık) ve y = 4 için benzer bir şey. Bu arada, herhangi bir rowsum colsum colzero veya rowzero negatif olduğunda iptal ediyorum.

Geçerli kart, yalnızca kalan tüm sütunların sütunları colzero ve rowzero'nun sıfır olması durumunda bir çözümdür. Bu yüzden sadece bunun için test ederim ve eğer varsa, çözümlere ekleyin. Yapım aşamasında herhangi bir olumsuz giriş olmayacaktır.