查找数组/序列中等于sum的最短组合

Question

我完全陷入困境,不知道如何解决这个问题.假设我有一个阵列

arr = [1, 4, 5, 10]

和一个数字

n = 8

我需要从arr内等于n的最短序列.所以例如在arr等于n之后的序列

c1 = 5,1,1,1
c2 = 4,4
c3= 1,1,1,1,1,1,1,1

所以在上面的例子中,我们的答案是c2,因为它是arr中等于sum的最短序列.

我不确定找到上述解决方案的最简单方法是什么？任何想法或帮助将非常感激.

谢谢!

编辑:

• 修复了数组
• 数组可能只有正值.
• 我不确定子集问题如何解决这个问题,可能是由于我自己的无知.子集算法总是给出等于和的最短序列吗？例如,子集问题会将c2识别为上述场景中的答案吗？

Answer 1

正如之前指出的，这是最小找零硬币问题，通常通过动态规划来解决。这是一个以时间复杂度 O(nC) 和空间复杂度 O(C) 解决的 Python 实现，其中n是硬币数量和C所需金额：

def min_change(V, C):
    table, solution = min_change_table(V, C)
    num_coins, coins = table[-1], []
    if num_coins == float('inf'):
        return []
    while C > 0:
        coins.append(V[solution[C]])
        C -= V[solution[C]]
    return coins

def min_change_table(V, C):
    m, n = C+1, len(V)
    table, solution = [0] * m, [0] * m
    for i in xrange(1, m):
        minNum, minIdx = float('inf'), -1
        for j in xrange(n):
            if V[j] <= i and 1 + table[i - V[j]] < minNum:
                minNum = 1 + table[i - V[j]]
                minIdx = j
        table[i] = minNum
        solution[i] = minIdx
    return (table, solution)

上述函数中V列出了可能的硬币和C所需的金额。现在，当您调用该min_change函数时，输出符合预期：

min_change([1,4,5,10], 8)
> [4, 4]