Проблемы в реализации "Задачи о назначениях"
Суть задачи о назначениях: с помощью некоторых махинаций сделать так, чтобы в каждом столбце и каждой строке матрицы было ровно одно минимальное значение.
Алгоритм:
- Отметить в каждой СТРОКЕ минимальное число. Если их несколько - выбрать только одно, желательно чтобы в СТОЛБЦЕ не было минимумов из других строк
- Отметить ПРОБЛЕМНЫЕ СТОЛБЦЫ - те, что с более чем 1 отмеченным минимумом или возможным минимумом (см. ниже)
- В СТРОКАХ с минимумами и возможными минимумами из ПРОБЛЕМНЫХ СТОЛБЦОВ выбираем минимум из НЕ ПРОБЛЕМНЫХ СТОЛБЦОВ и находим разницу этих двух минимумов (в программе это a_b)
- Увеличиваем ВСЕ числа из ПРОБЛЕМНЫХ СТОЛБЦОВ на наименьшую a_b
- Отмечаем возможные минимумы (те, что равны выделенному ранее числу из этой СТРОКИ)
- Если какой-либо СТОЛБЕЦ имеет возможный минимум и не имеет обычного минимума переходим к 6, иначе к 2
- Возможный минимум из СТОЛБЦА из пункта 5 делаем обычный минимум, а все остальные минимумы и возможные минимумы из той же СТРОКИ теперь обычные числа
- Если во всех СТОЛБЦАХ и СТРОКАХ есть ровно 1 минимальный элемент - задача решена, иначе возврат к пункту 0
Так вот. В чём проблема? Мой алгоритм правильно находит 1 новый нормальный минимум, а второй и далее отмечает неправильно или никак. Я не понимаю в каком if стоят не те условия или какой из массивов я не обнуляю в новой итерации while. Нужно чтобы программа решала хотябы данный пример
Содержимое file1.txt
9 6 3 6 6
11 8 9 11 7
11 7 1 9 3
19 6 6 14 11
15 13 5 15 13
Код:
#include <iostream>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <Windows.h>
#define GRAY SetColor(LightGray, Black)
#define LGREEN SetColor(LightGreen, Black)
#define LBLUE SetColor(LightBlue, Black)
#define ENDL cout << endl
using namespace std;
struct Number
{
int number;
int isMin;
};
enum ConsoleColor
{
Black = 0,
Blue = 1,
Green = 2,
Cyan = 3,
Red = 4,
Magenta = 5,
Brown = 6,
LightGray = 7,
DarkGray = 8,
LightBlue = 9,
LightGreen = 10,
LightCyan = 11,
LightRed = 12,
LightMagenta = 13,
Yellow = 14,
White = 15
};
void SetColor(ConsoleColor text, ConsoleColor background)
{
HANDLE hConsoleHandle = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hConsoleHandle, (WORD)((background << 4) | text));
}
/*
matr[][].number - само число
matr[][].isMin - если 2 то минимум (зелёный), если 1 то возможный минимум (синий), если -1 то был минимумом и больше им не станет 100%
numOfMinsJ[] - количество минимумов и возможных минимумов В СТОЛБЦАХ
numOfMinsI[] - количество минимумов В СТРОКАХ (кажется этот параметр у меня не используется)
I[] - номера СТРОК с несколькими минимумами и возможными минимумами (по сути заменяет проверки с numOfMinsI[], если бы он был нужен)
min[] - текущее минимальное число в строке
ai[] - минимум ВНЕ проблемных столбцов
bi[] - минимум В проблемных столбцах
a_b[] - разность ai и bi
pickedMin[] - если 1, то минимум из строки входит в проблемный столбец
n - размеронсть матрицы
i, j, J, k, kk - для for
ii - количество СТРОК с несколькими минимумами и возможными минимумами (отсчёт с 0)
jj - для нахождения неповторяющихся минимумов
step - номер итерации для while (временная мера чтобы не иметь бесконечный цикл)
numOfAllMins (и currect) - условие выхода из while
min_a_b - минимум из a_b
space - для определения размерности матрицы из файла
*/
void main()
{
setlocale(0, "ru");
Number** matr;
int* numOfMinsJ, * numOfMinsI, * min, * ai, * bi, * a_b, * pickedMin;
char space;
int n = 1, i, j, ii = 0, jj, I[100], J, k, kk, step = 0, numOfAllMins = 0, min_a_b;
bool currect = false;
fstream file("file1.txt");
while (!file.eof()) // рассчёт размерности матрицы
{
file.get(space);
if (space == ' ')
n++;
if (space == '\n')
break;
}
file.close();
numOfMinsJ = new int[n];
numOfMinsI = new int[n];
ai = new int[n];
bi = new int[n];
a_b = new int[n];
min = new int[n];
pickedMin = new int[n];
matr = new Number * [n];
for (i = 0; i < n; i++)
{
matr[i] = new Number[n];
numOfMinsJ[i] = 0;
numOfMinsI[i] = 0;
min[i] = 0;
}
cout << " Исходная матрица:\n";
file.open("file1.txt"); // считывание матрицы
if (file)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
file >> matr[i][j].number;
cout << setw(3) << matr[i][j].number << " ";
matr[i][j].isMin = 0;
}
ENDL;
}
}
ENDL;
file.close();
for (i = 0; i < n; i++) // нахождение минимумов
{
min[i] = matr[i][0].number;
for (j = 0; j < n; j++)
{
if (matr[i][j].number < min[i])
min[i] = matr[i][j].number;
}
for (j = 0; j < n; j++)
{
if (matr[i][j].number == min[i])
{
numOfMinsJ[j]++;
numOfMinsI[i]++;
matr[i][j].isMin = 2;
}
}
}
for (i = 0; i < n; i++) // нахождение неповторяющихя минимумов
{
if (numOfMinsI[i] > 1)
{
for (j = 0; j < n; j++)
{
if (numOfMinsJ[j] > 1)
{
for (J = 0; J < n; J++)
{
if (J != j)
if (matr[i][J].isMin == 2 && numOfMinsJ[J] == 1)
{
jj = J;
for (J = 0; J < n; J++)
if (J != jj && matr[i][J].isMin == 2)
{
matr[i][J].isMin = 0;
numOfMinsJ[J]--;
numOfMinsI[i]--;
}
}
}
}
}
}
if (numOfMinsI[i] > 1)
{
for (j = 0; j < n; j++)
{
if (matr[i][j].isMin == 2)
{
for (k = j + 1; k < n; k++)
{
if (matr[i][k].isMin = 2)
{
matr[i][k].isMin = 0;
numOfMinsJ[k]--;
numOfMinsI[i]--;
}
}
break;
}
}
}
}
for (i = 0; i < n; i++) // вывод
{
for (j = 0; j < n; j++)
{
if (matr[i][j].isMin == 2)
LGREEN;
cout << setw(3) << matr[i][j].number << " ";
GRAY;
}
ENDL;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
numOfAllMins++;
if (numOfAllMins == 2 * n)
currect = true;
/////////////////////////////////////////////////////////////////////
//// до сюда всё должно работать нормально
while (currect != true && step < 5)
{
step++;
ENDL;
cout << "step " << step << endl;
numOfAllMins = 0;
ENDL;
for (i = 0; i < n; i++) // определение СТОЛБЦОВ с несколькими минимумами
{
ai[i] = matr[i][0].number;
bi[i] = min[i];
a_b[i] = 999;
pickedMin[i] = 0;
for (j = 0; j < n; j++)
if (numOfMinsJ[j] > 1 && matr[i][j].isMin > 0)
pickedMin[i] = 1;
}
for (i = 0; i < n; i++) /// для СТРОК с выделенными минимумами ищем a_b
if (pickedMin[i] == 1)
for (j = 0; j < n; j++)
if (matr[i][j].number <= ai[i] && matr[i][j].number != min[i] && numOfMinsJ[j] <= 1)
{
ai[i] = matr[i][j].number;
a_b[i] = ai[i] - bi[i];
}
for (j = 0; j < n; j++) // вывод матрицы
cout << " ";
cout << " ai ai-bi \n";
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (matr[i][j].isMin == 2)
LGREEN;
if (matr[i][j].isMin == 1)
LBLUE;
cout << setw(3) << matr[i][j].number << " ";
GRAY;
}
if (pickedMin[i] == 1)
cout << " | " << setw(3) << ai[i] << " | " << setw(3) << a_b[i] << endl;
else
cout << " | - | - " << endl;
}
ENDL;
min_a_b = a_b[0]; // нахождение минимального a_b и запись в I[] номеров СТРОК с минимумами из ПРОБЛЕМНЫХ СТОЛБЦОВ
for (i = n - 1; i >= 0; i--)
{
if (a_b[i] <= min_a_b)
{
min_a_b = a_b[i];
I[ii] = i;
ii++;
}
}
for (kk = 0; kk < ii; kk++) //////// удаление повторяющихся элеентов из I[]
{ ////// такое ощущение, что они не удаляются
for (k = kk + 1; k < ii; k++)
if (I[kk] == I[k])
{
I[kk] = I[kk + 1];
k--;
ii--;
}
}
for (i = 0; i < n; i++) // вывод матрицы
{
for (j = 0; j < n; j++)
{
if (numOfMinsJ[j] > 1)
matr[i][j].number += min_a_b;
if (matr[i][j].isMin == 2)
LGREEN;
if (matr[i][j].isMin == 1)
LBLUE;
cout << setw(3) << matr[i][j].number << " ";
GRAY;
}
ENDL;
}
ENDL;
for (i = 0; i < n; i++) // снова находим минимум из строк
{
min[i] = matr[i][0].number;
for (j = 0; j < n; j++)
{
if (matr[i][j].number < min[i])
min[i] = matr[i][j].number;
}
}
for (i = 0; i < ii; i++) // в выдеоенных СТРОКАХ отмечаем возможные минимумы
for (j = 0; j < n; j++)
{
if (matr[I[i]][j].number == min[I[i]] && matr[I[i]][j].isMin == 0)
{
matr[I[i]][j].isMin = 1;
numOfMinsJ[j]++;
}
}
for (i = 0; i < n; i++) // выводим матрицу
{
for (j = 0; j < n; j++)
{
if (matr[i][j].isMin == 2)
LGREEN;
if (matr[i][j].isMin == 1)
LBLUE;
cout << setw(3) << matr[i][j].number << " ";
GRAY;
}
ENDL;
}
ENDL;
for (i = 0; i < n; i++) // забыл что тут точно происходит
{
for (j = 0; j < n; j++)
{
if (matr[i][j].isMin == 1 && matr[i][j].number == I[i])
{
matr[i][j].isMin == 0;
numOfMinsJ[j]--;
}
}
}
for (i = 0; i < ii; i++) // в выделенных строках находим возможный минимум, который находится в СТОЛБЦЕ без обычных минимумов
for (j = 0; j < n; j++) // отмечаем его как обычный и сбрасываем отметки со всех остальных чисел в строке
{
if (matr[I[i]][j].number == min[I[i]] && numOfMinsJ[j] == 1)
{
for (J = 0; J < n; J++)
{
if (J != j && matr[I[i]][J].number == min[I[i]])
{
numOfMinsJ[J]--;
matr[I[i]][J].isMin = -1;
}
}
matr[I[i]][j].isMin = 2;
}
}
for (j = 0; j < n; j++)
numOfAllMins += numOfMinsJ[j];
if (numOfAllMins == 2 * n)
currect = true;
//////////////////////////////////////////////////// отсюда вывод всез значений для проверки
ENDL;
cout << "matr[i][j].isMin";
ENDL;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
cout << setw(3) << matr[i][j].isMin << " ";
ENDL;
}
ENDL;
cout << "ii " << ii;
ENDL;
cout << "I[i] ";
for (i = 0; i < ii; i++)
cout << I[i] << " ";
ENDL;
cout << "numOfMinsJ[j] ";
for (j = 0; j < n; j++)
cout << numOfMinsJ[j] << " ";
ENDL;
cout << "numOfMinsI[i] ";
for (i = 0; i < n; i++)
cout << numOfMinsI[i] << " ";
ENDL;
cout << "min[i] ";
for (i = 0; i < n; i++)
cout << min[i] << " ";
ENDL;
cout << "numOfAllMins " << numOfAllMins;
}
}
Решение задачи на бумаге:
Как выглядит 1 итерация в консоли:
