Brute force with summation?

Question

Algorithms

Good afternoon. I really need help. Please let me know if it is possible to solve the following problem. There are certain 6 numbers: 256, 304, 397, 465, 477, 497. You need to add as many of them as you like to get the number 4600 (it is not necessary to use all the numbers). Is it possible? For example, using the number 256 - 13 times, 397 - 2 times, 477 - 1 time I get 4599. I understand that I need to go through the cycle, but I can’t figure out how to designate the conditions in my head.
Thank you in advance

Answer 1

Backtracking search and genetic algorithms.

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

Answer 2

You need a backtracking iteration . You can also try to get into genetic algorithms. :)