求和为一定值的第一个整数序列的算法
我有一个数字列表，我有一个总和值。例如，
list=[1, 2, 3, 5, 7, 11, 10, 23, 24, 54, 79]
sum=20
我想从这个列表中生成一个数字序列，这样序列就可以达到这个目标。为了帮助实现这一点，序列可以是任意长度的，并且允许重复。
result=[2,3,5,10]，或result=[1,1,2,3,3,5,5]，或result=[10,10]
我对这个问题做了很多研究，发现子集和问题很有趣。我的问题是，在一些方面，类似于子集和问题，因为我想找到一个产生目标和的数字子集。
然而，与子集求和问题不同的是，我只想找到一组数字，而子集求和问题会找到所有与目标求和的数字集（如果使用蛮力，则会以指数时间运行）。我想找到第一个能给我总数的集合。因此，在某种意义上，速度是一个因素。
此外，我希望算法具有一定程度的随机性（或伪随机性）。也就是说，如果我使用相同的列表运行算法并多次求和，我每次应该得到一组不同的数字。
实现这一点的最佳算法是什么？
附加说明：到目前为止，我所取得的成就是使用了一种简单的方法，在列表中循环，将其添加到每个值的组合中。这显然需要很长时间，我目前对此感到不太高兴。我希望有更好的方法做到这一点！
如果没有一个序列能给我精确的和，我对一个序列感到满意，这个序列能给我一个尽可能接近目标和的和。
共有3个答案
我会尝试将问题简化为一个较小集合的蛮力搜索。
- 将
列表从最小到最大排序
重复{
从列表的子集中随机抽取小于目标-总和按绘制值递增sum，将绘制值添加到结果列表中
}直到<代码>列表[0]
如果sum！=0，暴力搜索列表中的小组合，这些组合匹配总和和结果的小组合之间的差异
这种方法可能无法找到有效的解决方案，即使它们存在。然而，它可以很快找到解决方案，或者很快失败，然后不得不在更大的深度上使用整个集合，采用较慢的蛮力方法。
子集和问题不是寻找所有子集，而是确定是否存在某个子集。这是一个决策问题。NP中的所有问题都是这样的。甚至这个简单的问题也是NP完全问题。
这意味着，如果你想要一个精确的答案（子集必须精确地求和某个值），你将无法比任何子集求和算法做得更好（除非P=NP，否则它是指数的）。
正如其他人所说，这是一个NP问题
然而，这并不意味着小的改进是不可能的：
1在列表中吗？[1,1,1...]是解决方案。O（1）在排序列表中
删除大于目标和的列表元素。O（n）
是否存在（x%总和）=0的列表元素x？同样，简单的解决方案。O（n）
是否存在（x%y）==0的列表元素x，y？删除x.O（n^2）
（甚至可能：是否有任何列表元素x、y、z带有（x%y）==z或（xy）==z？移除x.O（n^3））
在使用完整递归之前，尝试一下是否可以用最小的偶数和最小的奇数求和
。
...
-
我正在寻找以下问题的答案。 给定一组整数（无重复项）和一个和，找出集合元素的所有可能组合，并求和。解的顺序并不重要（解{2,2,3}和{3,2,2}是相等的）。 请注意，最终组合不需要是集合，因为它可以包含重复。 示例：集合{2,3,5}和10 结果：{2, 2, 2, 2, 2}，{2,2,3,3}，{2,3,5}，{5,5} 我已经研究过子集和问题以及硬币兑换问题，但不能使它们适应我的需要。我
-
给定一个从1到n的序列，我想找到所有大小为m的唯一子序列，求和到n。子序列不需要是连续的。例如 到目前为止，我已经能够使用递归生成所有的子序列，但我的代码并不是只返回唯一的子序列，结果中有一些重复的子序列。 当用 结果是 正如您所看到的，{3,2}是{2,3}的副本。我如何改变我的代码，使它只返回唯一的序列？
-
问题是： 给出一个由n个整数组成的数组A、一个分离整数M和一个整数d。求a的一个连续子数组S，使子数组的大小小于或等于d，S中所有元素的和为M。返回a的索引，使左索引和右索引成为子数组S。所有的数字都是正的。 在这一点上我有80%的把握这是不可能的...我一直在看它，我想不出一个单一的方法来使这个工作，这可能是一个巨大的诡计问题吗？
-
我是新的java.here是我的代码。我确定我的字符串数组大小与nextint metod使用扫描仪。然后我添加了字符串与nextline metod.它似乎对我是正确的，但我不能看到我的第一个值的数组.这是什么问题在这个代码。
-
本文向大家介绍python计算一个序列的平均值的方法，包括了python计算一个序列的平均值的方法的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了python计算一个序列的平均值的方法。分享给大家供大家参考。具体如下： 如果序列是数组或者元祖可以简单使用下面的代码 希望本文所述对大家的Python程序设计有所帮助。
-
给定一组整数（正数或负数），我怎样才能找到一个和给定值相加的数字序列？ 示例：给定一个数字列表，我需要求和。我可以选择序列（数字可以重复使用）或。我正试图找到一种有效的方法来缩短序列的长度。 这就像(http://en.wikipedia.org/wiki/Subset_sum)但就我而言，数字可以重复使用。 这也有点像分区问题（找到所有可能的子集，求和到一个给定的数字），但在我的例子中有负值。