子集总和浮动消除
Subset Sum floats Elimations
我很乐意得到一些帮助。我有以下问题：
我得到了一个数字列表和一个目标数字。
subset_sum([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20)
我需要找到一种算法来找到所有组合起来的数字总和目标数字例如：20。
首先找到所有 int 等于 20
接下来例如这里的最佳组合是：
- 11.96 + 8.04
- 1 + 10 + 9
- 11.13 + 7.8 + 1.07
- 9 + 11
剩余价值15.04。
我需要一个只使用 1 个值一次的算法，它可以使用 1 到 n 个值来求和目标数。
我在 PHP 中尝试了一些递归，但内存很快耗尽（50k 值），因此 Python 中的解决方案会有所帮助（time/memory 明智）。
我很乐意在这里提供一些指导。
一个可能的解决方案是：Finding all possible combinations of numbers to reach a given sum
唯一的区别是我需要在已经使用的元素上放置一个标志，这样它就不会被使用两次，我可以减少可能的组合数量
感谢任何愿意提供帮助的人。
有很多方法可以考虑这个问题。
如果您执行递归，请确保首先确定您的最终情况，然后继续执行程序的其余部分。
首先想到的就是这个
<?php
subset_sum([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20);
function subset_sum($a,$s,$c = array())
{
if($s<0)
return;
if($s!=0&&count($a)==0)
return;
if($s!=0)
{
foreach($a as $xd=>$xdd)
{
unset($a[$xd]);
subset_sum($a,$s-$xdd,array_merge($c,array($xdd)));
}
}
else
print_r($c);
}
?>
这是可能的解决方案，但并不完美：
import itertools
import operator
from functools import reduce
def subset_num(array, num):
subsets = reduce(operator.add, [list(itertools.combinations(array, r)) for r in range(1, 1 + len(array))])
return [subset for subset in subsets if sum(subset) == num]
print(subset_num([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20))
输出：
[(20,), (11.96, 8.04), (9, 11), (11, 9), (1, 10, 9), (1, 10, 9), (7.8, 11.13, 1.07)]
免责声明：这不是一个完整的解决方案，它只是帮助您构建可能的子集的一种方法。它不会帮助您选择哪些是一起使用的（无需多次使用相同的项目并获得最低的余数）。
使用动态规划，您可以构建加起来等于给定总和的所有子集，然后您需要遍历它们并找到最适合您的子集组合。
要构建此存档，您可以（我假设我们只处理非负数）将项目放在一列中，从上到下并为每个元素计算所有加起来的子集总和或小于它的数字，并且仅包括列中位于您正在查看的位置或更高位置的项目。当您构建一个子集时，您将子集的总和（可能是给定的总和或更小）和子集中包含的项目都放入其节点中。因此，为了计算项目 [i] 的子集，您只需要查看为项目 [i-1] 创建的子集。他们每个人都有 3 个选项：
1) 子集的总和就是给定的总和--->保持子集不变，移到下一个。
2) 子集的总和小于给定的总和，但如果向其添加项目 [i] 则大于给定的总和 ---> 保持子集不变并继续下一个。
3) 子集的总和小于给定的总和，如果将项目 [i] 添加到它，它仍然会小于或等于给定的总和 ---> 保留子集的一份原样并创建另一个添加了项目[i]（既作为成员又添加到子集的总和）。
完成最后一项（第 [n] 项）后，查看您创建的子集 - 每个子集在其节点中都有其总和，您可以看到哪些子集等于给定的总和（哪些更小——您不再需要它们了）。
正如我在开头所写的那样 - 现在您需要弄清楚如何采用没有共享成员的子集的最佳组合。
基本上，您遇到的问题类似于经典的背包问题，但有另一个限制（并非每块石头都可以与其他所有石头一起使用）。也许这个限制真的有用，我不确定。
更多关于动态规划在这种情况下的优势
动态规划代替递归的基本思想是用内存占用来权衡操作的冗余度space。我的意思是说，复杂问题的递归（通常是类似回溯背包的问题，就像我们在这里遇到的那样）通常最终会计算相同的东西很多次，因为不同的计算分支没有彼此的概念操作和结果。动态编程保存结果并在构建 "bigger" 结果的过程中使用它们，依赖于以前的/"smaller" 的结果。因为栈的使用比递归更直接，你不会遇到递归维护函数状态时遇到的内存问题，但你确实需要处理大量存储的内存（有时你可以优化它）。
因此，例如在我们的问题中，试图组合一个子集，该子集将加起来达到所需的总和，以项目 A 开头的分支和以项目 B 开头的分支不知道彼此的操作。让我们假设项目 C 和项目 D 加起来等于总和，但它们中的任何一个单独添加到 A 或 B 都不会超过总和，并且 A 在解决方案中不与 B 一起使用（我们可以有总和 = 10， A=B=4, C=D=5 并且没有总和为 2 的子集（因此 A 和 B 不能在同一组中）。试图找出 A 的组的分支将（在尝试并拒绝 B 在其组中之后）添加 C (A+C=9)，然后添加 D，此时将拒绝该组并引用 (A+C+D= 14 > 总和 = 10)。 B 当然也会发生同样的情况 (A=B)，因为确定 B 的组的分支没有关于处理 A 的分支刚刚发生的事情的信息。所以实际上我们已经计算了 C+D 两次，而且还没有甚至还使用过它（我们将要第三次计算它以意识到它们属于自己的一组）。
注意：
在写这个答案时环顾四周，我遇到了一种我不熟悉的技术，可能对你来说是一个更好的解决方案：记忆。摘自 wikipedia：
memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
所以我有一个可能的解决方案：
#compute difference between 2 list but keep duplicates
def list_difference(a, b):
count = Counter(a) # count items in a
count.subtract(b) # subtract items that are in b
diff = []
for x in a:
if count[x] > 0:
count[x] -= 1
diff.append(x)
return diff
#return combination of numbers that match target
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print "--------------------------------------------sum_is(%s)=%s" % (partial, target)
return partial
else:
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
rest = subset_sum(remaining, target, partial + [n])
if type(rest) is list:
#repeat until rest is > target and rest is not the same as previous
def repeatUntil(subset, target):
currSubset = []
while sum(subset) > target and currSubset != subset:
diff = subset_sum(subset, target)
currSubset = subset
subset = list_difference(subset, diff)
return subset
输出：
--------------------------------------------sum_is([11.96, 8.04])=20
--------------------------------------------sum_is([1, 10, 9])=20
--------------------------------------------sum_is([7.8, 11.13, 1.07])=20
--------------------------------------------sum_is([20])=20
--------------------------------------------sum_is([9, 11])=20
[15.04]
不幸的是，这个解决方案只适用于一小部分列表。对于一个大列表，仍然试图将列表分成小块并进行计算，但答案并不完全正确。你可以在这里看到它的新线程：
Finding unique combinations of numbers to reach a given sum
我很乐意得到一些帮助。我有以下问题： 我得到了一个数字列表和一个目标数字。
subset_sum([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20)
我需要找到一种算法来找到所有组合起来的数字总和目标数字例如：20。 首先找到所有 int 等于 20 接下来例如这里的最佳组合是：
- 11.96 + 8.04
- 1 + 10 + 9
- 11.13 + 7.8 + 1.07
- 9 + 11
剩余价值15.04。
我需要一个只使用 1 个值一次的算法，它可以使用 1 到 n 个值来求和目标数。
我在 PHP 中尝试了一些递归，但内存很快耗尽（50k 值），因此 Python 中的解决方案会有所帮助（time/memory 明智）。 我很乐意在这里提供一些指导。
一个可能的解决方案是：Finding all possible combinations of numbers to reach a given sum
唯一的区别是我需要在已经使用的元素上放置一个标志，这样它就不会被使用两次，我可以减少可能的组合数量
感谢任何愿意提供帮助的人。
有很多方法可以考虑这个问题。 如果您执行递归，请确保首先确定您的最终情况，然后继续执行程序的其余部分。
首先想到的就是这个
<?php
subset_sum([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20);
function subset_sum($a,$s,$c = array())
{
if($s<0)
return;
if($s!=0&&count($a)==0)
return;
if($s!=0)
{
foreach($a as $xd=>$xdd)
{
unset($a[$xd]);
subset_sum($a,$s-$xdd,array_merge($c,array($xdd)));
}
}
else
print_r($c);
}
?>
这是可能的解决方案，但并不完美：
import itertools
import operator
from functools import reduce
def subset_num(array, num):
subsets = reduce(operator.add, [list(itertools.combinations(array, r)) for r in range(1, 1 + len(array))])
return [subset for subset in subsets if sum(subset) == num]
print(subset_num([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20))
输出：
[(20,), (11.96, 8.04), (9, 11), (11, 9), (1, 10, 9), (1, 10, 9), (7.8, 11.13, 1.07)]
免责声明：这不是一个完整的解决方案，它只是帮助您构建可能的子集的一种方法。它不会帮助您选择哪些是一起使用的（无需多次使用相同的项目并获得最低的余数）。
使用动态规划，您可以构建加起来等于给定总和的所有子集，然后您需要遍历它们并找到最适合您的子集组合。
要构建此存档，您可以（我假设我们只处理非负数）将项目放在一列中，从上到下并为每个元素计算所有加起来的子集总和或小于它的数字，并且仅包括列中位于您正在查看的位置或更高位置的项目。当您构建一个子集时，您将子集的总和（可能是给定的总和或更小）和子集中包含的项目都放入其节点中。因此，为了计算项目 [i] 的子集，您只需要查看为项目 [i-1] 创建的子集。他们每个人都有 3 个选项：
1) 子集的总和就是给定的总和--->保持子集不变，移到下一个。
2) 子集的总和小于给定的总和，但如果向其添加项目 [i] 则大于给定的总和 ---> 保持子集不变并继续下一个。
3) 子集的总和小于给定的总和，如果将项目 [i] 添加到它，它仍然会小于或等于给定的总和 ---> 保留子集的一份原样并创建另一个添加了项目[i]（既作为成员又添加到子集的总和）。
完成最后一项（第 [n] 项）后，查看您创建的子集 - 每个子集在其节点中都有其总和，您可以看到哪些子集等于给定的总和（哪些更小——您不再需要它们了）。
正如我在开头所写的那样 - 现在您需要弄清楚如何采用没有共享成员的子集的最佳组合。 基本上，您遇到的问题类似于经典的背包问题，但有另一个限制（并非每块石头都可以与其他所有石头一起使用）。也许这个限制真的有用，我不确定。
更多关于动态规划在这种情况下的优势
动态规划代替递归的基本思想是用内存占用来权衡操作的冗余度space。我的意思是说，复杂问题的递归（通常是类似回溯背包的问题，就像我们在这里遇到的那样）通常最终会计算相同的东西很多次，因为不同的计算分支没有彼此的概念操作和结果。动态编程保存结果并在构建 "bigger" 结果的过程中使用它们，依赖于以前的/"smaller" 的结果。因为栈的使用比递归更直接，你不会遇到递归维护函数状态时遇到的内存问题，但你确实需要处理大量存储的内存（有时你可以优化它）。
因此，例如在我们的问题中，试图组合一个子集，该子集将加起来达到所需的总和，以项目 A 开头的分支和以项目 B 开头的分支不知道彼此的操作。让我们假设项目 C 和项目 D 加起来等于总和，但它们中的任何一个单独添加到 A 或 B 都不会超过总和，并且 A 在解决方案中不与 B 一起使用（我们可以有总和 = 10， A=B=4, C=D=5 并且没有总和为 2 的子集（因此 A 和 B 不能在同一组中）。试图找出 A 的组的分支将（在尝试并拒绝 B 在其组中之后）添加 C (A+C=9)，然后添加 D，此时将拒绝该组并引用 (A+C+D= 14 > 总和 = 10)。 B 当然也会发生同样的情况 (A=B)，因为确定 B 的组的分支没有关于处理 A 的分支刚刚发生的事情的信息。所以实际上我们已经计算了 C+D 两次，而且还没有甚至还使用过它（我们将要第三次计算它以意识到它们属于自己的一组）。
注意： 在写这个答案时环顾四周，我遇到了一种我不熟悉的技术，可能对你来说是一个更好的解决方案：记忆。摘自 wikipedia：
memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
所以我有一个可能的解决方案：
#compute difference between 2 list but keep duplicates
def list_difference(a, b):
count = Counter(a) # count items in a
count.subtract(b) # subtract items that are in b
diff = []
for x in a:
if count[x] > 0:
count[x] -= 1
diff.append(x)
return diff
#return combination of numbers that match target
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print "--------------------------------------------sum_is(%s)=%s" % (partial, target)
return partial
else:
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
rest = subset_sum(remaining, target, partial + [n])
if type(rest) is list:
#repeat until rest is > target and rest is not the same as previous
def repeatUntil(subset, target):
currSubset = []
while sum(subset) > target and currSubset != subset:
diff = subset_sum(subset, target)
currSubset = subset
subset = list_difference(subset, diff)
return subset
输出：
--------------------------------------------sum_is([11.96, 8.04])=20
--------------------------------------------sum_is([1, 10, 9])=20
--------------------------------------------sum_is([7.8, 11.13, 1.07])=20
--------------------------------------------sum_is([20])=20
--------------------------------------------sum_is([9, 11])=20
[15.04]
不幸的是，这个解决方案只适用于一小部分列表。对于一个大列表，仍然试图将列表分成小块并进行计算，但答案并不完全正确。你可以在这里看到它的新线程： Finding unique combinations of numbers to reach a given sum