mathematical-optimization - 验证是否可以根据序列 (a,b,c) 的组合生成数字 X

Question

我快要发疯了，试图找出一种方法来制作一个不会尝试每一种组合的程序。一个简单的例子:我想知道是否可以通过将系列 (2,5,10,20) 中的数字相加来生成 11，是否有一种简单的方法可以做到这一点而无需尝试每一种可能性？在这种情况下，我们可以用三个 2 和一个 5 来完成。谢谢

Answer 1

我想我想出了某种解决方案

1. 您必须按从高到低的顺序排列 list 。它给了我们 [20, 10, 5, 2]
2. 然后，我们将使用某种堆栈。

我们从 n=0 开始

一个。您将列表的第 n 个元素放在堆栈的顶部。

如果进入堆栈的数字总和大于目标数字，则删除堆栈的最后一个元素并返回到点 a。 n=n+1。如果你从栈中取出的元素是你的小号，那么你也取出下面的元素，返回到a点。 n=(你集合中最后删除的数字的索引)+1

如果不是，则再尝试添加一次，然后返回b点。

这个算法是递归的，当你从你的堆栈中删除最后一个数字时它会停止，这个数字是你的较低数字(那么你不能从你的集合中生成数字)，或者当你的堆栈中的数字总和等于你的目标号码(然后你可以从你的集合中生成它)

运行示例:目标 11，设置 [20,10,5,2]

• 堆栈状态:空，n=0
• 将 20 放入堆栈:堆栈状态:[20] > 11，从堆栈中移除 20 => n=1
• 将 10 入栈 : 栈状态 : [10] < 11, n=1
• 将 10 放入堆栈:堆栈状态:[10, 10] > 11，从堆栈中移除 10 => n=2
• 将 5 放入堆栈:堆栈状态:[10,5] > 11，从堆栈中移除 5 => n=3
• 将 2 放入堆栈:堆栈状态:[10,2] > 11，从堆栈中删除 2 和 10 => n=2
• 将 5 入栈 : 栈状态 : [5] < 11, n=2
• 将 5 入栈:栈状态:[5,5] < 11, n=2
• 将 5 放入堆栈:堆栈状态:[5,5,5] > 11，从堆栈中移除 5 => n=3
• 将 2 放入堆栈:堆栈状态:[5,5,2] > 11，从堆栈中删除 2 和 5 => n=3
• 将 2 入栈:栈状态:[5,2] < 11, n=3
• 将 2 入栈:栈状态:[5,2,2] < 11, n=3
• 将 2 放入堆栈:堆栈状态:[5,2,2,2] = 11，你赢了