1. Акция на весь декабрь! Получай оплату х2 за уникальные статьи, объемом от 200 слов, если в заголовке темы и теле статьи присутствует слово Python
    Скрыть объявление

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

Тема в разделе "Delphi - FAQ", создана пользователем pikkk, 9 май 2008.

  1. pikkk

    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
    Решить не проблема, но как реализовать в делфи я не знаю :( , поэтому здесь и пишу
     
  2. Yason

    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 (да-да, умножение не нужно).
    После полного перебора будет достаточно найти минимальную сумму и соответствующий ей вариант.
     
  3. pikkk

    pikkk Гость

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

    Yason Гость

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

    pikkk Гость

    Спасибо за алгоритм, я всё реализлвал :)
    ПС: не нашёл где плюсик ставить :unsure:
     
Загрузка...
Похожие Темы - Перебор элементов матрицы
  1. pbnoob
    Ответов:
    9
    Просмотров:
    4.852
  2. 123456789igor
    Ответов:
    1
    Просмотров:
    1.570
  3. sima12
    Ответов:
    4
    Просмотров:
    1.771
  4. iivvnn
    Ответов:
    4
    Просмотров:
    1.859
  5. Altaya
    Ответов:
    10
    Просмотров:
    2.811

Поделиться этой страницей