То, что вы пытаетесь решить, является вариантом проблемы с монетой . Здесь вы ищете наименьшее количество изменений или минимальное количество монет на сумму до данной суммы.
Рассмотрим простой случай, когда ваш массив
c = [1, 2, 3]
Вы пишете 5 как комбинацию элементов из C и хотите знать, какая самая короткая такая комбинация. Здесь C - набор значений монет, а 5 - сумма, за которую вы хотите получить сдачу.
Запишем все возможные комбинации:
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 2 + 2
1 + 1 + 3
2 + 3
Обратите внимание, что до повторного заказа две комбинации одинаковы, например, 2 + 3 = 3 + 2.
Здесь есть потрясающий результат, который на первый взгляд неочевиден, но его очень легко доказать. Если у вас есть последовательность монет / значений, представляющая собой последовательность минимальной длины, которая суммирует до заданной суммы, независимо от того, как вы разбили эту последовательность, эти две части также будут последовательностями минимальной длины для соответствующих сумм.
Например, если c[3] + c[1] + c[2] + c[7] + c[2] + c[3] добавить до S и мы знаем, что 6 - это последовательность элементов минимальной длины от c, которая добавляет до S, тогда, если вы разделите
|
S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3]
|
у вас есть то, что 4 является минимальной длиной для последовательностей, которые в сумме составляют c[3] + c[1] + c[2] + c[7] и 2 минимальной длины для последовательностей, которые в сумме составляют c[2] + c[3].
|
S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3]
|
= S_left + S_right
Как это доказать? В противовес предположим, что длина S_left не является оптимальной, то есть есть более короткая последовательность, которая в сумме составляет S_left. Но тогда мы могли бы написать S как сумму этой более короткой последовательности и S_right, что противоречит тому факту, что длина S минимальна. □
Так как это верно независимо от того, как вы разбили последовательность, вы можете использовать этот результат для построения рекурсивного алгоритма, который следует принципам парадигмы динамического программирования (решение небольших задач, возможно, пропуская вычисления, которые не будут использоваться, памятка или отслеживание вычисленных значений и, наконец, объединение результатов).
ОК, поэтому в приведенном выше небольшом примере это то, как мы должны решить проблему с помощью подхода динамического программирования: предположим, что мы хотим найти кратчайшую последовательность элементов из c = [1, 2, 3] для записи суммы 5. Мы решаем подзадачи, полученные путем вычитания одной монеты: 5 - 1, 5 - 2 и 5 - 3, берем наименьшее решение этих подзадач и добавляем 1 (недостающая монета).
Так что мы можем написать что-то вроде
shortest_seq_length([1, 2, 3], 5) =
min( shortest_seq_length([1, 2, 3], 5-1),
shortest_seq_length([1, 2, 3], 5-2),
shortest_seq_length([1, 2, 3], 5-3)
) + 1
Удобно написать алгоритм снизу вверх, начиная с меньших значений сумм, которые можно сохранить и использовать для формирования больших сумм. Мы просто решаем задачу для всех возможных значений, начиная с 1 и до нужной суммы.
Вот код на Python:
def shortest_seq_length(c, S):
res = {0: 0} # res contains computed results res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
res[i] = min([res[i-x] for x in c if x<=i]) + 1
return res[S]
Теперь это работает, за исключением случаев, когда мы не можем заполнить структуру памятки для всех значений i. Это тот случай, когда у нас нет значения 1 в c, поэтому, например, мы не можем сформировать сумму 1, если c = [2, 5], и с помощью вышеуказанной функции мы получим
shortest_seq_length([2, 3], 5)
# ValueError: min() arg is an empty sequence
Таким образом, чтобы решить эту проблему, можно, например, использовать try / catch:
def shortest_seq_length(c, S):
res = {0: 0} # res is the dictionary containing results for each sum res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
try:
res[i] = min([res[i-x] for x in c if x<=i and res[i-x] is not None]) +1
except:
res[i] = None # takes care of error when [res[i-x] for x in c if x<=i] is empty
return res[S]
Попробуйте:
print(shortest_seq_length([2, 3], 5))
# 2
print(shortest_seq_length([1, 5, 10, 25], 37))
# 4
print(shortest_seq_length([1, 5, 10], 30))
# 3
print(shortest_seq_length([1, 5, 10], 25))
# 3
print(shortest_seq_length([1, 5, 10], 29))
# 7
print(shortest_seq_length([5, 10], 9))
# None
Одним небольшим улучшением алгоритма является пропуск шага вычисления минимума, когда сумма равна одному из значений / монет, но это можно сделать лучше, если мы напишем цикл для вычисления минимума. Это улучшение, однако, не улучшает общую сложность, которая составляет O(mS), где m = len(c).