Я решал проблемы на конкурентном веб-сайте кодирования, когда наткнулся на это. Проблема гласит, что:
В этой игре есть N уровней и M типов доступного оружия. Уровни пронумерованы от 0 до N-1, а оружие пронумеровано от 0 до M-1. Вы можете очистить эти уровни в любом порядке. На каждом уровне требуется некоторое подмножество этого M оружия, чтобы очистить этот уровень. Если на определенном уровне вам нужно купить x новых видов оружия, вы заплатите за это x ^ 2 монет. Также обратите внимание, что вы можете перенести все имеющееся у вас оружие на следующий уровень. Изначально у вас нет оружия. Сможете ли вы узнать минимальное количество монет, необходимое для прохождения всех уровней?
Формат ввода Первая строка ввода содержит 2 целых числа, разделенных пробелами: N = количество уровней в игре M = количество видов оружия
Далее следует N строк. В i-й из этих строк находится двоичная строка длины M. Если j-й символ строки эта строка равна 1, это означает, что нам нужно оружие типа j, чтобы очистить i-й уровень.
Ограничения 1 <= N <= 20 1 <= M <= 20
Выходной формат Выведите единственное целое число, которое и является ответом на проблему.
Пример TestCase 1
Вход
1 4
0101
Выход
4
Объяснение В этой игре всего один уровень. Нам понадобится 2 вида оружия - 1 и 3. Поскольку изначально Бен у него нет оружия, ему придется купить его, что будет стоить ему 2 ^ 2 = 4 монеты.
Пример TestCase 2
Вход
3 3
111
001
010
Выход
3
Объяснение В игре 3 уровня. Для 0-го уровня (111) требуются все 3 вида оружия. 1-й уровень (001) требует только оружия типа 2. Для 2-го уровня требуется только оружие типа 1. Если мы очистим уровни в заданном порядке (0-1-2), общая стоимость = 3 ^ 2 + 0 ^ 2 + 0 ^ 2 = 9 монет. Если мы очистим уровни в порядке 1-2-0, это будет стоить = 1 ^ 2 + 1 ^ 2 + 1 ^ 2 = 3 монеты, что является оптимальным способом.
Подход
Я смог выяснить, что мы можем рассчитать минимальную стоимость, пройдя двоичные строки таким образом, чтобы мы покупали минимально возможное оружие на каждом уровне.
Одним из возможных способов может быть обход массива двоичных строк и вычисление стоимости для каждого уровня, когда массив уже расположен в правильном порядке. Правильный порядок должен быть, когда строки уже отсортированы, то есть 001, 010, 111, как в случае вышеуказанного тестового примера. Обход массивов в таком порядке и суммирование стоимости для каждого уровня дает правильный ответ.
Кроме того, метод сортировки в java отлично работает для сортировки этих двоичных строк перед запуском цикла в массиве для суммирования стоимости для каждого уровня.
Arrays.sort(weapons);
Этот подход отлично работает для некоторых тестовых примеров, однако более половины тестовых примеров по-прежнему не работают, и я не могу понять, что не так с моей логикой. Я использую поразрядные операторы, чтобы вычислить количество оружия, необходимого на каждом уровне, и вернуть их квадрат.
К сожалению, я не вижу тестовых примеров, которые не работают. Любая помощь приветствуется.
Покупая оружие для уровня, вы хотели бы покупать только то оружие, которое необходимо для этого уровня, покупка другого оружия, которое не нужно, увеличит стоимость, так зачем вам это делать?
Допустим, у вас есть уровни 0001 и 1111. Если вы покупаете только то оружие, которое вам нужно, у вас будет стоимость 1 * 1 + 3 * 3 = 10, но если вы купите два оружия для первого уровня и два для второго, у вас будет 2 * 2 + 2 * 2 = 8, что явно лучше.
Итак, как вы заявили, оптимальный способ - это упорядочить уровни таким образом, чтобы на каждом уровне нужно было покупать наименьшее количество дополнительного оружия. Однако это не обязательно отсортированный порядок строк. Возможно, вам стоит разобрать BitSet
и отсортировать по количеству установленных битов.
@ThomasTimbul Согласен с вами. Правильный способ - подсчитать количество установленных битов вместо обычной сортировки. Однако даже после сортировки строк по количеству установленных битов все тестовые примеры не проходят.
Разве это не относится к CodeReview или другому сайту SE?
Я думаю, что сортировка набора битов становится более сложной, потому что вы на самом деле ищете минимальное количество установленных бит дополнительный, учитывая все предыдущие биты. Таким образом, после прохождения всех уровней, на которых нужно было купить одно оружие (что было бы неизбежной стоимостью 2 за уровень), вы можете затем вычесть все эти биты из оставшихся уровней перед сортировкой остатка для следующей группы уровней. . Эта следующая группа снова будет иметь наименьшее количество установленных битов дополнительный.
Сомневаюсь, что проблему можно свести к простой задаче сортировки.
Я не понимаю, как можно упростить задачу сортировки, и @SaiBot задает важный вопрос, но фраза «оружие, которое вам нужно» предполагает, что вы не можете покупать дополнительное оружие. Кстати: у второго тестового примера есть два решения для данной стоимости (1-2-0 и 2-1-0).
@JeremyGrand Не совсем. Пожалуйста, прочтите мета-сообщение это для уточнения.
Кроме того, можно ли дважды вернуться на тот же уровень? Например, очистите его часть, затем сделайте что-нибудь еще, а затем вернитесь к нему и очистите его полностью.
@lexicore, так что ни один из них? Насколько этот вопрос может быть интересным, я не думаю, что он здесь, по крайней мере, не в такой форме. Это слишком много для help me with my homework
(даже если это не домашнее задание как таковое), чем для how to solve a technical issue
.
@JeremyGrand С моей точки зрения, это онтопический как «программный алгоритм».
@JeremyGrand Даже учитывая, что это домашнее задание, ОП продемонстрировал добросовестную попытку. Также вопрос можно интерпретировать как проблему с существующей реализацией.
@JeremyGrand Подводя итог, я лично не голосовал за закрытие. Мне нравится этот вопрос, он показывает интересную проблему. И я хотел бы знать ответ.
Логика этой проблемы заключается в том, что каждый раз вам нужно найти минимальное количество установленных битов, соответствующих двоичной строке, которая будет содержать оружие, уже полученное на уровне.
Например: у нас есть данные как 4 3 101-2 бит 010-1 бит 110-2 бит 101-2 бит теперь, поскольку 010 имеет минимальные биты, мы сначала вычисляем стоимость для него, а затем обновляем текущий шаблон (с помощью побитового ИЛИ), поэтому текущий шаблон равен 010 Затем мы находим следующие минимальные установленные биты по отношению к текущему шаблону Я использовал логику, сначала используя XOR для текущего шаблона и данного числа, затем используя AND с текущим числом (A ^ B) & A поэтому биты становятся такими после операции (101 ^ 010) и 101-> 101-2 бит (110 ^ 010) и 110-> 100-1 бит теперь мы знаем, что минимальный бит равен 110, мы выбираем его и вычисляем стоимость, обновляем шаблон и т. д. Этот метод возвращает стоимость строки относительно текущего шаблона.
private static int computeCost(String currPattern, String costString) {
int a = currPattern.isEmpty()?0:Integer.parseInt(currPattern, 2);
int b = Integer.parseInt(costString, 2);
int cost = 0;
int c = (a ^ b) & b;
cost = (int) Math.pow(countSetBits(c), 2);
return cost;
}
Это тоже неправильно. Учитывайте уровни 11100
, 11110
, 11111
, а также 00011
. Решение потребует, чтобы 00011
сначала заплатил 4, после чего ему в любом случае пришлось бы заплатить 9 за первые три бита одновременно, в общей сложности 13. Принимая во внимание, что если мы начнем с оплаты 9 за 11100
, мы можем продолжить с 11110
, а затем платить 11111
. всего 9 + 1 + 1 = 11.
Это можно решить с помощью динамического программирования.
Состояние будет битовой маской оружия, которым мы сейчас владеем.
Переходы будут состоять в том, чтобы попытаться очистить каждый из возможных уровней n
по очереди из текущего состояния, получить дополнительное оружие, которое нам нужно, и заплатить за него.
В каждом из результирующих состояний n
мы берем минимальную стоимость текущего способа его достижения и всех ранее наблюдаемых способов.
Когда у нас уже есть какое-то оружие, некоторые уровни фактически не потребуют покупки дополнительного оружия; такие переходы будут автоматически игнорироваться, поскольку в таком случае мы приходим в то же состояние, заплатив ту же стоимость.
Запускаем на состоянии нулей m
, заплатив 0
.
Конечное состояние - это поразрядное ИЛИ всех заданных уровней, и минимальные затраты на его получение - это ответ.
В псевдокоде:
let mask[1], mask[2], ..., mask[n] be the given bit masks of the n levels
p2m = 2 to the power of m
f[0] = 0
all f[1], f[2], ..., f[p2m-1] = infinity
for state = 0, 1, 2, ..., p2m-1:
current_cost = f[state]
current_ones = popcount(state) // popcount is the number of 1 bits
for level = 1, 2, ..., n:
new_state = state | mask[level] // the operation is bitwise OR
new_cost = current_cost + square (popcount(new_state) - current_ones)
f[new_state] = min (f[new_state], new_cost)
mask_total = mask[1] | mask[2] | ... | mask[n]
the answer is f[mask_total]
Сложность заключается в времени O(2^m * n)
и памяти O(2^m)
, что должно быть приемлемо для m <= 20
и n <= 20
в большинстве онлайн-судей.
@SaiBot Все возможные последовательности имеют номер n!
и 20! = 2,432,902,008,176,640,000
. С другой стороны, 2^20
- это только 1,048,576
. Экономия за счет использования динамического программирования заключается в преобразовании n!
в 2^n
: состояние динамического программирования отбрасывает часть в каком порядке и оставляет только часть куплен или нет.
Идея динамической оптимизации @Gassa может быть расширена с помощью А *, оценивая минимальную и максимальную оставшуюся стоимость, где
minRemaining(s)=bitCount(maxState-s)
maxRemaining(s)=bitCount(maxState-s)^2
Начните с очереди с приоритетом - и основывайте ее на cost + minRemaining - только с пустым состоянием, а затем замените состояние из этой очереди, которое не достигло maxState, максимум на n новых состояний на основе n уровней:
Следить за bound=min(cost(s)+maxRemaining(s))
в очереди,
и инициализируйте все расходы с помощью bitCount(maxState)^2+1
extract state with lowest cost
if state!=maxState
remove state from queue
for j in 1..n
if (state|level[j]!=state)
cost(state|level[j])=min(cost(state|level[j]),
cost(state)+bitCount(state|level[j]-state)^2
if cost(state|level[j])+minRemaining(state|level[j])<=bound
add/replace state|level[j] in queue
else break
Идея состоит в том, чтобы избежать тупиков. Итак, рассмотрим пример из комментария
11100 cost 9 min 2 max 4
11110 cost 16 min 1 max 1
11111 cost 25 min 0 max 0
00011 cost 4 min 3 max 9
bound 13
remove 00011 and replace with 11111 (skipping 00011 since no change)
11111 cost 13 min 0 max 0
11100 cost 9 min 2 max 4
11110 cost 16 min 1 max 1
remove 11100 and replace with 11110 11111 (skipping 11100 since no change):
11111 cost 13 min 0 max 0
11110 cost 10 min 1 max 1
bound 11
remove 11110 and replace with 11111 (skipping 11110 since no change)
11111 cost 11 min 0 max 0
bound 11
Количество операций должно быть аналогично динамической оптимизации в худшем случае, но во многих случаях будет лучше - и я не знаю, может ли случиться худший случай.
Можете ли вы также купить оружие, которое вам не понадобится для следующего уровня?