我完全陷入困境，不知道如何解决这个问题。假设我有一个数组
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 的最短序列。
我不确定找到上述解决方案的最简单方法是什么？任何想法或帮助将不胜感激。
谢谢！
编辑：
正如之前所指出的，这是最小找零硬币问题，通常通过动态规划来解决。这是一个以时间复杂度 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 所指出的，这就是硬币找零（change-giving，change-making）的问题。
一般来说，他们提出的动态规划解决方案是最佳解决方案——无论是就（可证明！）始终使用最少的项目产生所需的总和，还是就执行速度而言。如果您的基数是任意的，则使用动态规划解决方案。
但是，如果您的基数“不错”，则可以使用更简单的贪心算法。
例如，澳大利亚货币系统使用$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]
这是子集和问题的一种变体。在您的问题中，您可以多次选择一个项目。您仍然可以使用类似的想法通过使用动态编程技术来解决此问题。其基本思想是设计一个函数 F(k, j)，使得 F(k, j) = 1 表示存在来自 arr 的序列，其和为 j，长度为 k。
形式上，基本情况是 F(k, 1) = 1，如果存在 i，则 arr[i] = k。对于归纳情况，如果存在 i，则 F(k, j) = 1，使得 arr[i] = m，并且 F(k-1, jm) = 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□</p>
由于无论您如何拆分序列都是如此，您可以使用此结果来构建遵循动态编程范式原则的递归算法（解决较小的问题，同时可能跳过不会使用的计算、记忆或跟踪计算值，最后结合结果）。
由于这种维持子问题最优性的特性，硬币问题也被称为“表现出最优子结构”。
好的，所以在上面的小例子中，我们将如何使用动态编程方法解决问题：假设我们想要找到最短的元素序列c = [1, 2, 3]来编写 sum 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. 当我们没有 in 的值时就是这种情况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 contains 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]
或者没有尝试/捕获：
def shortest_seq_length(c, S):
res = {0: 0} # res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
prev = [res[i-x] for x in c if x<=i and res[i-x] is not None]
if len(prev)>0:
res[i] = min(prev) +1
else:
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
不仅要显示长度，还要显示最小长度硬币的组合：
from collections import defaultdict
def shortest_seq_length(coins, sum):
combos = defaultdict(list)
combos[0] = [[]]
for i in range(1, sum+1):
for x in coins:
if x<=i and combos[i-x] is not None:
for p in combos[i-x]:
comb = sorted(p + [x])
if comb not in combos[i]:
combos[i].append(comb)
if len(combos[i])>0:
m = (min(map(len,combos[i])))
combos[i] = [combo for i, combo in enumerate(combos[i]) if len(combo) == m]
else:
combos[i] = None
return combos[sum]
total = 9
coin_sizes = [10, 8, 5, 4, 1]
shortest_seq_length(coin_sizes, total)
# [[1, 8], [4, 5]]
要显示所有序列，请删除最小计算：
from collections import defaultdict
def all_seq_length(coins, sum):
combos = defaultdict(list)
combos[0] = [[]]
for i in range(1, sum+1):
for x in coins:
if x<=i and combos[i-x] is not None:
for p in combos[i-x]:
comb = sorted(p + [x])
if comb not in combos[i]:
combos[i].append(comb)
if len(combos[i])==0:
combos[i] = None
return combos[sum]
total = 9
coin_sizes = [10, 5, 4, 8, 1]
all_seq_length(coin_sizes, total)
# [[4, 5],
# [1, 1, 1, 1, 5],
# [1, 4, 4],
# [1, 1, 1, 1, 1, 4],
# [1, 8],
# [1, 1, 1, 1, 1, 1, 1, 1, 1]]
该算法的一个小改进是当总和等于其中一个值/硬币时跳过计算最小值的步骤，但是如果我们编写一个循环来计算最小值，这可以做得更好。O(mS)然而，这并没有提高m = len(c).