жадный алгоритм матрица 0 \ 1

Question

Я учусь для алгоритма экзамена, и я не могу найти способ решить следующую проблему:

ВХОД: Положительные целые числа r1, r2 .... гп и c1, c2 .... cn

OUTPUT: матрица с n по n с такими номерами 0/1, что для всех i сумма i-й строки в A равна ri и сумма i-го столбца в A есть ci, если такая матрица существует. Рассмотрим следующий жадный алгоритм, который строит строку за строкой. Предположим, что были построены первые строки i-1. Пусть aj - число 1 в j-м столбце в первых строках i-1. Столбец ri с максимальным значением cj-aj присваивается 1 в строке, а остальным столбцов назначаются 0. То есть, столбцам, которым по-прежнему нужно больше всего 1, даны 1. Формально доказать, что этот алгоритм корректен с использованием аргумента обмена.

Так что я пытался сделать так, как с большинством жадных проблем, с которыми я столкнулся, состоит в том, чтобы обернуть его в индукции, предположим, что строки до i-й строки в жадном решении и оптимальное решение одинаковы и затем попытайтесь изменить i + 1-й ряд, чтобы он соответствовал жадным и доказывал, что он не создаст менее оптимальное решение для оптимального заданного. то сохраняйте его для итераций k-i до тех пор, пока все решения не будут похожи.

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

Затем я пробовал использовать другой подход, предполагая, что у меня есть набор шагов в жадном и своп целом алгоритме (который в основном та же идея, что и первый), и все же мне не удалось найти в котором гарантируется, что я не создал менее оптимальное решение.

Заранее благодарим за любую помощь.

Answer 1

Рассмотрите некоторые входы r и c и матрицу S, которая их удовлетворяет.

Отбросьте содержимое последней строки в S, чтобы получить новую матрицу S(n-1). Если мы подали S(n-1) в жадный алгоритм и попросили заполнить эту последнюю строку, он, очевидно, восстановил бы удовлетворительное решение.

Ну, теперь выбросьте содержимое последних двух строк в S, чтобы получить S(n-2). Поскольку мы знаем, что существует удовлетворительное решение, мы знаем, что нет j такой, что c(j) - a(j) > 2 и число j такое, что c(j)-a(j) == 2 меньше, чем r(n-1). Из этого следует, что жадный алгоритм установит A[n-1, j] = 1 для последнего набора j, а также некоторые другие j, для которых c(j)-a(j) = 1. Но поскольку мы знаем, что есть удовлетворительное решение, должно быть, что число j с c(j) - a(j) == 1 после заполнения n-1-го ряда составляет точно r(n) и, следовательно, является выполнимым.

Во всяком случае, мы можем распространить это вниз: в S(n-k-1) должно быть так, что:

• Есть нет j такие, что c(j) - a(j) > k+1
• может быть наиболее r(n-k) многие j такие, что c(j) - a(j) = k+1 ,
• и Sum(c(j) - a(j)) == Sum(r(i), i >= n-k)

Таким образом, после жадный алгоритм обработал n-k ю строку, оно должно быть так, что

• не является любыми j таким образом, что c(j) - a(j) > k
• может быть самым r(n-k+1) многие j таким образом, что c(j) - a(j) = k,
• и Sum(c(j) - a(j)) == Sum(r(i), i >= n-k+1)

Следовательно, когда k = 0, нет какой-либо j таким образом, что c(j) - a(j) > 0