我完全陷入困境，不知道如何解决这个问题。假设我有一个阵列
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的最短序列。
我不确定找到上述解决方案的最简单方法是什么？任何想法或帮助将非常感激。
谢谢！
编辑：
正如之前所指出的那样是minimum change coin problem，通常用动态编程解决。这是一个在时间复杂度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]
为了将来发现这个问题的人的利益 -
正如Oscar Lopez和Priyank Bhatnagar所指出的那样，这就是硬币变化（变更，变革）的问题。
一般来说，他们提出的动态编程解决方案是最佳解决方案 - 无论是（可证明！）总是使用最少的项目和执行速度产生所需的总和。如果您的基数是任意的，那么使用动态编程解决方案。
但是，如果你的基数是“好的”，那么一个更简单的贪婪算法就可以了。
例如，澳大利亚货币系统使用$100, $50, $20, $10, $5, $2, $1, $0.50, $0.20, $0.10, $0.05的面额。通过重复给出最大的变化单位，直到剩余金额为零（或小于5美分），可以给出任何金额的最佳变化。
这是贪婪算法的一个有益实现，说明了这个概念。
def greedy_give_change (denominations, amount):
# Sort from largest to smallest
denominations = sorted(denominations, reverse=True)
# number of each note/coin given
change_given = list()
for d in denominations:
while amount > d:
change_given.append(d)
amount -= d
return change_given
australian_coins = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05]
change = greedy_give_change(australian_coins, 313.37)
print (change) # [100, 100, 100, 10, 2, 1, 0.2, 0.1, 0.05]
print (sum(change)) # 313.35
对于原始帖子（denominations = [1, 4, 5, 10]和amount = 8）中的具体示例，贪婪的解决方案不是最优的 - 它将给出[5, 1, 1, 1]。但是贪婪的解决方案比动态编程解决方案更快更简单，所以如果你可以使用它，你应该！
这个问题被称为最小硬币变化问题。
您可以使用动态编程来解决它。这是伪代码：
Set MinCoin[i] equal to Infinity for all of i
MinCoin[0] = 0
For i = 1 to N // The number N
For j = 0 to M - 1 // M denominations given
// Number i is broken into i-Value[j] for which we already know the answer
// And we update if it gives us lesser value than previous known.
If (Value[j] <= i and MinCoin[i-Value[j]]+1 < MinCoin[i])
MinCoin[i] = MinCoin[i-Value[j]]+1
Output MinCoin[N]
这是子集和问题的变体。在您的问题中，您可以多次选择一个项目。您仍然可以使用类似的想法通过使用动态prorgamming技术来解决此问题。基本思想是设计函数F（k，j），使得F（k，j）= 1意味着存在来自arr的序列，其和为j且长度为k。
形式上，基本情况是F（k，1）= 1，如果存在i，则arr [i] = k。对于归纳情况，F（k，j）= 1，如果存在i，则arr [i] = m，并且F（k-1，j-m）= 1。
F（k，n）= 1的最小k是您想要的最短序列的长度。
通过使用动态编程技术，您可以在不使用递归的情况下计算函数F.通过跟踪每个F（k，j）的附加信息，您还可以重建最短的序列。
你要解决的是硬币变化问题的变种。在这里，您需要寻找最小的变化量，或者总计达到给定量的最小硬币数量。
考虑一下你的数组的简单情况
c = [1, 2, 3]
你写了5作为C元素的组合，想知道什么是最短的组合。这里C是硬币值的集合，5是您想要改变的金额。
让我们写下所有可能的组合：
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 2 + 2
1 + 1 + 3
2 + 3
请注意，两个组合在重新排序时是相同的，因此例如2 + 3 = 3 + 2。
这里有一个令人敬畏的结果，一见钟情并不明显，但很容易证明。如果您有任何序列的硬币/值是最小长度的序列，总计达到给定的数量，无论您如何拆分此序列，这两个部分也将是相应金额的最小长度序列。
例如，如果c[3] + c[1] + c[2] + c[7] + c[2] + c[3]加起来S并且我们知道6是来自c的最小长度的元素序列加起来S然后如果你分裂
|
S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3]
|
你有4是加起来c[3] + c[1] + c[2] + c[7]和2的序列的最小长度，加起来c[2] + c[3]的序列的最小长度。
|
S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3]
|
= S_left + S_right
怎么证明这个？通过矛盾，假设S_left的长度不是最佳的，那就是有一个较短的序列加起来S_left。但是我们可以把S写成这个较短序列和S_right的总和，因此与S的长度最小的事实相矛盾。 □
因为无论你如何拆分序列都是如此，你可以使用这个结果来构建一个遵循动态编程范式原则的递归算法（解决较小的问题，同时可能跳过不会使用的计算，记忆或跟踪计算值，最后组合结果）。
好的，所以在上面的小例子中，这就是我们如何用动态编程方法解决问题：假设我们想要从c = [1, 2, 3]找到最短的元素序列来编写和5。我们解决了通过减去一个硬币得到的子问题：5 - 1，5 - 2和5 - 3，我们采用这些子问题的最小解，并加1（丢失的硬币）。
所以我们可以写类似的东西
shortest_seq_length([1, 2, 3], 5) =
min( shortest_seq_length([1, 2, 3], 5-1),
shortest_seq_length([1, 2, 3], 5-2),
shortest_seq_length([1, 2, 3], 5-3)
) + 1
自下而上编写算法很方便，从较小的总和值开始，可以保存并用于形成更大的总和。我们只是解决从1开始并上升到所需总和的所有可能值的问题。
这是Python中的代码：
def shortest_seq_length(c, S):
res = {0: 0} # res contains computed results res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
res[i] = min([res[i-x] for x in c if x<=i]) + 1
return res[S]
现在这个工作除了我们无法填充i的所有值的memoization结构的情况。当我们在1中没有值c时就是这种情况，所以例如如果1和我们得到的上述函数我们不能形成总和c = [2, 5]
shortest_seq_length([2, 3], 5)
# ValueError: min() arg is an empty sequence
因此，为了解决这个问题，可以使用try / catch：
def shortest_seq_length(c, S):
res = {0: 0} # res is the dictionary containing results for each sum res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
try:
res[i] = min([res[i-x] for x in c if x<=i and res[i-x] is not None]) +1
except:
res[i] = None # takes care of error when [res[i-x] for x in c if x<=i] is empty
return res[S]
试试看：
print(shortest_seq_length([2, 3], 5))
# 2
print(shortest_seq_length([1, 5, 10, 25], 37))
# 4
print(shortest_seq_length([1, 5, 10], 30))
# 3
print(shortest_seq_length([1, 5, 10], 25))
# 3
print(shortest_seq_length([1, 5, 10], 29))
# 7
print(shortest_seq_length([5, 10], 9))
# None
算法的一个小改进是当总和等于其中一个值/硬币时跳过计算最小值的步骤，但如果我们编写一个循环来计算最小值，这可以做得更好。然而，改善并不能改善O(mS)所在的m = len(c)的总体复杂性。