optimization - 优化特定数字以达到价值

Question

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

欢迎任何帮助或提示！

标签： optimizationdivide

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)]