Минимизировать стоимость трансформации

Question

У меня возникла следующая проблема, но я не могу найти решение для нее.

Утверждение:

Есть N бокалов. Предполагается, что каждый бокал вина имеет бесконечную емкость. Количество вина в каждом бокале является положительным ненулевым целым числом, где единица измерения - мл. Движение типа 1 определяется как перенос одного мл из стекла i в стакан j. Ход типа 2 определяется как выбрасывание одного мл из стакана, т.е. Все ходы типа 1 имеют стоимость одного. Все ходы типа 2 имеют стоимость k. Учитывая начальное количество вина в каждом бокале, нам нужно сделать несколько ходов двух видов, чтобы убедиться, что количество вина в каждом бокале - это простое число (или ноль). Выведите минимальную стоимость такой трансформации.

Как решить эту проблему? Есть идеи для возможного решения?

Answer 1

Этот тип проблемы решаем при динамическом программировании и аналогичен вычислению минимального расстояния редактирования строки, которое вы можете решить с помощью алгоритма Хиршберга.

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

Например, предположим, что у вас есть итоги, такие как 16 14 8. Первый шаг - вы должны перечислить каждую возможную простую комбинацию: { 37 0 0 } { 31 7 0 } и т. Д. Затем вы используете алгоритм Хиршберга для вычисления минимального редактирования. Расстояние до каждого из этих кандидатов.

Answer 2

Вот примерный набросок моей идеи:

Простые числа распределяются следующим образом: x / ln (x).

Также используйте границы на этой странице, чтобы найти ближайший штрих к количеству вина в бокале.

После того, как вы найдете эти числа, вы можете свести проблему к графику с ребрами, у которых есть затраты, представляющие значения для перемещения из одного стакана в другой (ваш тип 1). И узлами будут сами очки.

С этого момента у вас осталась проблема с графиком, и вы должны думать о путях минимальной стоимости на этом графике. Ваша цель - найти путь минимальной стоимости, который приведет к состоянию, в котором все очки являются простыми числами.

Если есть бокалы, которые мешают вам это делать, выпейте их (ход типа 2), вино хорошо для вас:)

ОБНОВЛЕНИЕ:

Я напишу здесь некоторые действительные мысли, которые мы обсуждали в чате:

• было упомянуто двустороннее соответствие, и есть вероятность того, что проблема может быть сведена к этому
• сначала вы можете получить простые разбиения между каждыми двумя стеклами (простые разбиения суммы каждых двух очков), и эти разбиения являются ребрами на графике. Затем вы также добавляете ребра для ходов типа 2. Вы можете как-то связать затраты, а затем запустить алгоритм минимального потока для решения проблемы.
• проблема также может заключаться в том, что вам нужны все эти ребра, упомянутые выше, поскольку оптимальное решение может не подразумевать принятие оптимального простого соотношения для каждого из очков