C# 0-1 Knapsack Vấn đề với số tiền và số 0 đã biết trong tập hợp

Question

Tôi có một bảng giá trị 5x5 từ 0 đến 3 bao gồm tất cả các giá trị không xác định. Tôi biết cả tổng của các giá trị và số lượng 0 cho mỗi hàng và cột. Làm thế nào tôi sẽ đi về giải quyết vấn đề này knapsack 0-1 bằng cách sử dụng C# và lấy các giải pháp có thể đáp ứng các khoản tiền được biết đến và số lượng không? Các bảng sẽ luôn luôn là năm hàng và năm cột, do đó, nó không phải là khá một chiếc ba lô truyền thống.

Ví dụ, nói rằng chúng ta đầu vào:

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 

Chúng tôi sẽ có được điều này như một giải pháp khả thi:

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

gì loại thuật toán tôi nên sử dụng trong tình huống khá lạ này? Tôi cũng sẽ phải viết một lớp chỉ để liệt kê các hoán vị?

Chỉnh sửa để làm rõ: vấn đề không phải là tôi không thể liệt kê các khả năng; đó là tôi không có đầu mối làm thế nào để đi về hiệu quả xác định hoán vị thêm vào một số tùy ý trong khi có chứa số lượng quy định của số không và tối đa là 5 mục.

Answer 1

Ở đây có mã. Nếu bạn cần bất kỳ nhận xét nào, hãy hỏi:

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

Nhanh như thế nào? Tôi chỉ thử nghiệm một ngây thơ "thử khá nhiều bất cứ điều gì" với một số hủy bỏ sớm nhưng ít hơn sẽ có thể, và nó đã được khá nhanh (ít hơn một phần nghìn giây). Nó đã đưa ra giải pháp:

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

Nếu đó là một giải pháp có thể chấp nhận đối với bạn, tôi có thể gửi mã (hoặc chỉ thảo luận về nó, nó khá dài dòng nhưng ý tưởng cơ bản là tầm thường)

chỉnh sửa: nó cũng là trivially mở rộng để liệt kê tất cả các giải pháp. Nó tìm thấy 400 trong số họ trong 15 mili giây, và tuyên bố rằng không có nhiều hơn thế. Đúng không?

---

Những gì tôi đã làm, đã bắt đầu từ 0,0 và thử tất cả các giá trị tôi có thể điền vào tại nơi đó (0 mặc dù min (3, rowsum [0])), điền vào nó nó (trừ nó từ rowsum [y] và colsum [x] và trừ một từ rowzero [y] và colzero [x] nếu giá trị bằng không), sau đó đệ quy làm điều này cho 0,1; 0,2; 0,3; sau đó tại 0,4, tôi có một trường hợp đặc biệt khi tôi chỉ điền vào các hàng còn lại nếu nó không âm (nếu không, hủy bỏ phép thử hiện tại - tức là đi lên trong cây đệ quy), và một cái gì đó tương tự khi y = 4. Trong thời gian đó, tôi hủy bỏ khi bất kỳ rowum colsum colzero hoặc rowzero trở thành tiêu cực.

Bảng hiện tại là một giải pháp nếu và chỉ khi tất cả các hàng còn lại cột cột của colzero và rowzero bằng không. Vì vậy, tôi chỉ cần kiểm tra cho điều đó, và thêm nó vào các giải pháp nếu nó là một. Nó sẽ không có bất kỳ mục tiêu tiêu cực bằng cách xây dựng.