C # 0-1 Рюкзак Проблема с известной суммой и количеством нулей в наборе - PullRequest
5 голосов
/ 04 сентября 2011

У меня есть таблица значений 5x5 от 0 до 3 включительно со всеми неизвестными значениями. Я знаю как сумму значений, так и количество нулей для каждой строки и столбца. Как мне решить эту проблему с ранцем 0-1, используя C #, и найти возможные решения, которые удовлетворяют известным суммам и количеству нулей? Таблицы всегда будут состоять из пяти строк и пяти столбцов, так что это не совсем традиционный рюкзак.

Например, скажем, мы вводим:

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

Мы бы получили это как возможное решение:

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

Какой тип алгоритма мне следует использовать в этой довольно странной ситуации? Должен ли я также написать класс для перечисления перестановок?

Редактировать для уточнения: проблема не в том, что я не могу перечислить возможности; это то, что я понятия не имею, как эффективно определять перестановки, добавляющие к произвольной сумме, в то время как содержит указанное число нулей и максимум 5 элементов.

Ответы [ 2 ]

3 голосов
/ 04 сентября 2011

Здесь есть код. Если вам нужен какой-либо комментарий, не стесняйтесь спрашивать:

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;
        }
    }
}
1 голос
/ 04 сентября 2011

Как быстро это должно быть? Я только что проверил наивное «попробуй почти все» с некоторыми ранними прерываниями, но меньше, чем было бы возможно, и это было довольно быстро (менее миллисекунды). Это дало решение:

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

Если это приемлемое для вас решение, я могу опубликовать код (или просто обсудить его, он довольно многословен, но основная идея тривиальна)

edit: тривиально расширяемо для перечисления всех решений. Он нашел 400 из них за 15 миллисекунд и утверждает, что их не более того. Это правильно?


То, что я сделал, началось с 0,0 и попробовал все значения, которые я мог заполнить в этом месте (от 0 до min (3, rowum [0])), заполнил его (вычтя из rowum [y] и colsum [x] и вычитание одного из rowzero [y] и colzero [x], если значение было равно нулю), то рекурсивно сделать это для 0,1; 0,2; 0,3; затем в 0,4 у меня есть особый случай, когда я просто заполняю оставшуюся строку, если она неотрицательна (в противном случае, прерываю текущую попытку - то есть поднимаюсь в дереве рекурсии), и что-то подобное для случая, когда y = 4. В то же время, я прекращаю, когда какой-либо rows colsum colzero или rowzero становится отрицательным.

Текущее правление является решением в том и только в том случае, если все оставшиеся ряды столбцов столбцов столбцов и строк равно нулю. Поэтому я просто проверяю это и добавляю его в решения, если оно одно. По конструкции не будет отрицательных записей.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...