已知集合中0和0个数的背包问题
本文关键字：0个 背包问题 集合 | 更新日期: 2023-09-27 18:07:33
我有一个5x5的值表，从0到3，包括所有未知值。我知道每一行每一列的值的和和0的个数。我该如何使用c#解决这个0-1背包问题，并检索满足已知和和0个数的可能解?表格总是五行五列，所以它不是一个传统的背包。
例如，假设我们输入:
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个项目。
代码如下:如果您需要任何评论，请随时提问:
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;
}
}
}
它必须有多快?我刚刚测试了一个天真的"尝试几乎任何东西"，有一些早期的中止，但比可能的要少，而且它非常快(不到一毫秒)。它给出了解决方案:
[[ 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:它也可以简单地扩展到枚举所有解。它在15毫秒内发现了400个，并声称没有更多。对吗?
我所做的是，从0,0开始，尝试在该位置填充所有值(0到min(3, rowsum[0]))，填充它(从rowsum[y]和colsum[x]中减去它，从rowzero[y]和colzero[x]中减去1，如果值为0)，然后递归地对0,1执行此操作;0, 2;0, 3;然后在(0,4)处，我有一个特殊的情况，如果它是非负的，我只填充剩余的行和(否则，中止当前的尝试-即在递归树中向上)，当y=4时，情况类似。同时，当任何rowsum colsum colzero或rowzero变为负值时，终止。
当前板是一个解决方案当且仅当所有剩余的行和列和colzero's和rowzero's为零。我测试一下，如果它是1，就把它加到解中。通过构造，它不会有任何负条目