Оптимизация конкретных чисел для достижения значения

Question

Я пытаюсь создать программу, которая при заданных конкретных значениях (скажем, 1, 4 и 10) будет пытаться получить, сколько каждого значения необходимо для достижения определенной суммы, скажем, 19.
Он всегда будет пытаться использовать как можно больше высоких значений, поэтому в этом случае результат должен быть 10 * 1, 4 * 2, 1 * 1.Я пытался обдумать это, но не смог получить алгоритм, который мог бы работать ...

Любая помощь или подсказки приветствуются!

Answer 1

Если кому-то нужен простой алгоритм, я нашел один способ:
sort the values, in descending order keep track on how many values are kept for each value, do: if the sum is equal to the target, stop if it isn't the first value, remove one of the previous values while the total sum of values is smaller than the objective: add the current value once

Хорошего дня!

(Как упомянул ювянт, это не сработает, еслипропускает большие числа и использует только меньшие! Я постараюсь улучшить его и выложу новую версию, когда получу его на работу)

Answer 2

Вот решение Python, которое пробует все варианты, пока один не найден.Если вы передадите значения, которые он может использовать в порядке убывания, первым найденным будет тот, который использует максимально возможные значения:

def solve(left, idx, nums, used):
        if (left == 0):
            return True
        for i in range(idx, len(nums)):
            j = int(left / nums[idx])
            while (j > 0):
                used.append((nums[idx], j))
                if solve(left - j * nums[idx], idx + 1, nums, used):
                    return True
                used.pop()
                j -= 1
        return False      
solution = []        
solve(19, 0, [10, 4, 1], solution)
print(solution) # will print [(10, 1), (4, 2), (1, 1)]