优化特定数字以实现价值

Question

我正在尝试制作一个程序，当给定特定值（比如 1、4 和 10）时，将尝试获取每个值需要多少才能达到一定数量，比如 19。
它将始终尝试使用尽可能多的高值，因此在本例中，结果应为 10*1、4*2、1*1。我试着考虑一下，但最终无法找到一个可行的算法...

欢迎任何帮助或提示！

Answer 1

这是一个 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)]

Answer 2

如果有人需要一个简单的算法，我找到的一种方法是：
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

祝你有愉快的一天！

（正如 juviant 提到的那样，如果跳过较大的数字并且只使用较小的数字，这将不起作用！我会尝试改进它并 post 一个新版本当我让它工作时）

优化特定数字以实现价值

Optimizing specific numbers to reach value

optimization

divide