在等于总和的数组/序列中找到最短的组合 [英] Finding shortest combinations in array/sequence that equals sum

问题描述

我完全被困住了，不知道如何解决这个问题。假设我有一个数组

I'm totally stuck and have no idea how to go about solving this. Let's say I've an array

arr = [1, 4, 5, 10]

和一个数字

n = 8

我需要arr内等于n的最短序列。因此，例如arr中的以下序列等于n

I need shortest sequence from within arr which equals n. So for example following sequences within arr equals n

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

因此在上述情况下，我们的答案是c2，因为它是arr中等于和的最短序列。

So in above case, our answer is c2 because it's shortest sequences in arr that equals sum.

我不确定找到上述解决方案的最简单方法是什么？

I'm not sure what's the simplest way of finding a solution to above? Any ideas, or help will be really appreciated.

谢谢！

编辑：

• 固定数组


• 数组可能仅具有正值。


• I我不确定子集问题如何解决此问题，可能是由于我自己的无知。子集算法是否总是给出等于和的最短序列？例如，在上述情况下，子集问题会将c2标识为答案吗？

推荐答案

之前指出的是最小找零硬币问题，通常通过动态编程来解决。这是解决时间复杂度O（nC）和空间复杂度O（C）的Python实现，其中 n 是硬币数量， C 所需金额：

As has been pointed before this is the minimum change coin problem, typically solved with dynamic programming. Here's a Python implementation solved in time complexity O(nC) and space complexity O(C), where n is the number of coins and C the required amount of money:

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 函数时，输出将按预期进行：

In the above functions V is the list of possible coins and C the required amount of money. Now when you call the min_change function the output is as expected:

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

这篇关于在等于总和的数组/序列中找到最短的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！