до 268 года до нашей эры в древнем Риме было шесть основных монет:
унция (1 унция)
секстанс( 2 унции)
квадранс( 3 унции)
семис ( 6 унций)
асс (12 унций)
однажды римлянин Флавий взял с собой по две монеты каждого из шести номиналов( всего 12 момент) и отправился на рынок. сколькими способами он сможет без сдачи оплатить своими монетами покупку стоимостью 48 унций? монеты одного номинала считайте одинаковыми
python
def count_ways(weights):
dp = [[0] * 6 for _ in range(49)]
dp[0][0] = 1
for j in range(1, 6):
for i in range(49):
dp[i][j] = dp[i][j - 1]
if i - weights[j - 1] >= 0:
dp[i][j] += dp[i - weights[j - 1]][j]
return dp[48][5]
weights = [1, 2, 3, 6, 12]
result = count_ways(weights)
print(result)
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет