@lemuriec

Перебор с суммированием?

Добрый день. Очень нужна помощь. Подскажите возможно ли решить следующую задачу. Есть определенные 6 чисел: 256, 304, 397, 465 , 477, 497 . Нужно сколько угодно их складывая получить число 4600 (не обязательно использовать все числа). Это возможно? Например используя число 256 - 13 раз, 397 - 2 раза, 477 - 1 раз получаю 4599. Понимаю что нужно циклом перебирать, но как обозначить условия не могу в голове сообразить.

Заранее благодарю
  • Вопрос задан
  • 238 просмотров
Решения вопроса 1
longclaps
@longclaps
Фтопку перебор с возвратом и генетические алгоритмы.
n = 4600
dp = [''] * (n + 1)
dp[0] = '0'
for step in 256, 304, 397, 465, 477, 497:
    for i in range(n - step, -1, -1):
        if dp[i]:
            for j in range(i + step, n + 1, step):
                if not dp[j]:
                    dp[j] = f'{dp[i]}+{step}*{(j - i) // step}'
print(dp[-1][2:] if dp[-1] else 'извини, не смогла')
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
usdglander
@usdglander
Yippee ki-yay
Вам нужен перебор с возвратом. Можно так же попробовать упороться в генетические алгоритмы. :)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы