Поскольку вы не показываете свой собственный код, я дам вам несколько идей без кода.Если вам нужна дополнительная помощь, покажите больше своей работы, тогда я могу показать вам код Python, который решает вашу проблему.
Ваша проблема подходит для возврата .Википедия определяет этот алгоритм следующим образом:
Обратное отслеживание - это общий алгоритм для нахождения всех (или некоторых) решений некоторых вычислительных проблем , в частности проблем удовлетворения ограничений ,который постепенно строит кандидатов на решения и отказывается от кандидата («возвратных путей»), как только он определяет, что кандидат не может быть завершен до допустимого решения.
и
Возврат может быть применен только к задачам, которые допускают концепцию «частичного решения-кандидата» и относительно быстрый тест того, возможно ли его завершение до действительного решения.
Ваша проблема удовлетворяетэти требования.На каждом этапе вам нужно выбрать один из оставшихся весов и один из двух уровней шкалы.Когда вы помещаете выбранный вес на выбранную чашку, вы определяете, удовлетворяется ли соответствующая буква из входной строки.Если нет, вы отказываетесь от выбора веса и сковороды.Если это так, вы продолжаете, выбирая другой вес и панорамирование.
Ваша общая процедура сначала вводит и подготавливает данные.Затем он вызывает рекурсивную процедуру, которая выбирает один вес и одну кастрюлю на каждом уровне.Некоторая информация, необходимая каждому уровню, может быть помещена в изменяемые глобальные переменные, но было бы более понятно, если вы передадите всю необходимую информацию в качестве параметров.Каждый вызов рекурсивной подпрограммы должен передавать:
- весовые коэффициенты, еще не использованные
- входная строка L / R, еще не использованная
- текущее состояниевеса на сковородках в формате, который можно легко распечатать после завершения (возможно, массив упорядоченных пар веса и сковороды)
- текущий дисбаланс весов сковороды.Это можно рассчитать из предыдущего параметра, но время будет сэкономлено, если передать это отдельно.Это будет сумма весов на правой чашке минус сумма весов на левой чашке (или наоборот).
Ваш базовый случай для рекурсии - это когда неиспользованные веса и неиспользованныеПисьма пусты.Затем вы завершили поиск и можете распечатать решение и выйти из программы.В противном случае вы перебираете все комбинации одного из неиспользованных гирь и одного из сковородок.Для каждой комбинации рассчитайте, какой будет новый дисбаланс, если вы поместите этот вес на эту чашу.Если этот новый дисбаланс согласуется с соответствующей буквой, вызовите подпрограмму рекурсивно с соответствующим образом измененными параметрами.Если нет, ничего не делайте для этого веса и панорамирования.
У вас еще есть несколько вариантов, которые нужно сделать перед кодированием, например, структура данных для неиспользуемых весов.Покажите мне свои собственные усилия по написанию кода, и я дам вам свой код на Python.
Имейте в виду, что это может быть медленным для большого количества весов.Для n весов и двух панелей общее количество способов размещения весов на панелях составляет n! * 2**n (то есть факториал и возведение в степень).Для n = 50 это больше 3e79, слишком много, чтобы сделать.Возврат позволяет избежать большинства групп выбора, так как выбор отклоняется как можно скорее, но мой алгоритм все еще может быть медленным.Там может быть лучший алгоритм, чем возврат, но я не вижу его.Похоже, что ваша проблема решена путем обратного отслеживания.
Теперь, когда вы приложили больше усилий, вот мой неоптимизированный код Python 3.Это работает для всех приведенных вами примеров, хотя я получил другое правильное решение для вашего третьего примера.
def weights_on_pans():
def solve(unused_weights, unused_tilts, placement, imbalance):
"""Place the weights on the scales using recursive
backtracking. Return True if successful, False otherwise."""
if not unused_weights:
# Done: print the placement and note that we succeeded
for weight, pan in placement:
print(weight, 'L' if pan < 0 else 'R')
return True # success right now
tilt, *later_tilts = unused_tilts
for weight in unused_weights:
for pan in (-1, 1): # -1 means left, 1 means right
new_imbalance = imbalance + pan * weight
if new_imbalance * tilt > 0: # both negative or both positive
# Continue searching since imbalance in proper direction
if solve(unused_weights - {weight},
later_tilts,
placement + [(weight, pan)],
new_imbalance):
return True # success at a lower level
return False # not yet successful
# Get the inputs from standard input. (This version has no validity checks)
cnt_weights = int(input())
weights = {int(item) for item in input().split()}
letters = input()
# Call the recursive routine with appropriate starting parameters.
tilts = [(-1 if letter == 'L' else 1) for letter in letters]
solve(weights, tilts, [], 0)
weights_on_pans()
Основной способ ускорить этот код - избежать операций O(n) при вызове solve во внутреннем цикле.Это означает, что, возможно, изменив структуру данных unused_weights и изменив ее, placement и, возможно, unused_tilts / later_tilts будут изменены для использования O(1) операций.Эти изменения усложнят код, поэтому я их не делал.