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

Question

[lemuriec]

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

Заранее благодарю

Answer 1

[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 'извини, не смогла')

Comments

[Lander]

Молодец! Только вроде никто не просил готового решения.
Думаете вы один тут умете в программирование?

[longclaps]

Lander, чёрт, черт, черт!!!
Ведь говорила мне мама: никогда, никогда не выкладывай на тостер решений, если это может бросить тень на чью-либо способность программировать.
Прости меня, Lander, ты всё умеешь и во всём лучше меня!

[lemuriec]

Спасибо большое))
А есть еще вот такое решение:

import numpy as np
 
ls = np.array((256, 304, 397, 465, 477, 497))
val = 4600
 
def main():
    k = np.zeros_like(ls)
    
    def check(i=0):
        v = sum(ls * k)
        if v == val:
            raise ValueError(k)
        elif v > val:
            k[i] = 0
            k[i + 1] += 1
            check(i + 1)        
    
    while True:
        k[0] += 1
        print(k)
        check()
 
main()

[lemuriec]

Вот понимать бы еще что делает ваш код я бы с ума сошел от радости))

[longclaps]

lemuriec, ну вот это и есть перебор с возвратом. Медленнее, зато более приспособлен к большим n.
Ну да на больших n при достаточном выборе шагов есть еще более быстрое решение.

[longclaps]

lemuriec, попробуй поиграться с мелкими числами и посмотреть, как оно:

n = 5
dp = [''] * (n + 1)
dp[0] = '0'
for step in 2, 3:
    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)
print(dp[-1][2:] if dp[-1] else 'извини, не смогда')

Answer 2

[Lander]

Вам нужен перебор с возвратом. Можно так же попробовать упороться в генетические алгоритмы. :)

Comments

[GavriKos]

ген.алгоритмы тут кстати неплохо подойдут так. Когда то решал задачу с генерацией формулы используя заданные числа и базовые арифметические операции - и вполне неплохо справлялись генетические алгоритмы. Не считая конечно ситуации когда решение есть, но алгоритм забрел в тупик - он то его найдет, но искать будет долго.