Перебор элементов матрицы

[pikkk]

Добрый день Уважаемые программисты!
Мне тут поставили вроде бы лёгкую задачу, которую я никак не могу решить.
Соль в следующем:
дана матрица А:6 на 3:
6 5 6 5 4 7
7 6 9 6 5 10
8 4 8 3 8 12
Нужно найти такую матрицу Х, состоящую из нулей и единиц(причём в каждом столбце может быть только одна единица) при которой сумма произведений элементов матриц(А*Х) будет минимальной. Рекомендовали перебор, я просмотрел наверно уже все алгоритмы, но так и не понял как тут применить.
Помогите, Пожалуйста, заранее благодарен.

Ответ:
я забыл про одно условие: что сумма по строкам должна быть два
То есть, ответ здесь такой:
0 0 1 0 0 1
1 0 0 0 1 0
0 1 0 1 0 0

Чтобы при умножений элементов такой матрицы(массива) на исходную
0 0 6 0 0 7
7 0 0 0 5 0
0 4 0 3 0 0
и минимум будет: 7+4+6+3+5+7=32
Решить не проблема, но как реализовать в делфи я не знаю , поэтому здесь и пишу

 

[Yason]

Если в одном столбце может быть ровно одна единица, то для трёх строк и шести столбцов всего будет 3^6=729 вариантов.
Матрицу с единицами для экономии памяти можно представить в виде массива длиной 6, в ячейках которого будет номер строки, в которой должна быть единица, т.е. для
0 0 1 0 0 1
1 0 0 0 1 0
0 1 0 1 0 0
это будет (если индексация начинается с 1)
2 3 1 3 2 1

Таким образом, задача сведётся к перебору номеров а-ля
1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 1 3
1 1 1 1 2 1
1 1 1 1 2 2
1 1 1 1 2 3
.....
3 3 3 3 3 3
Условие "сумма по строкам=2" можно учесть, проверяя, чтобы в текущем варианте каждый номер встречался ровно два раза, т.е. вышеприведённое сведётся к чему-то типа
1 1 2 2 3 3
1 2 2 3 3 1
2 2 3 3 1 1
1 3 2 3 2 1
и т.п.

Для каждого варианта нужно хранить сумму соответствующих элементов матрицы A (да-да, умножение не нужно).
После полного перебора будет достаточно найти минимальную сумму и соответствующий ей вариант.

 

[pikkk]

Хм.. алгоритм понятен, вот тока как это в Делфи реализовать, еще чтобы на каждой перестановке он сумму записывал...

 

[Yason]

pikkk, я бы сделал динамический массив record'ов {массив, сумма}. Хотя даже нет, все варианты хранить совершенно не нужно, достаточно хранить самый лучший и текущий.
Но если вопрос не в алгоритме, а в языке -- то, видимо, стоит почитать букварь по Delphi.

 

[pikkk]

Спасибо за алгоритм, я всё реализлвал
ПС: не нашёл где плюсик ставить