我很乐意得到一些帮助。我有以下问题：我得到了一个数字列表和一个目标数字。
subset_sum([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20)
我需要找到一个算法，找到所有组合的数字将和目标数字（例如： 20）。首先找到所有int等于20，接下来，例如，这里的最佳组合是：
剩余值15.04。
我需要一个只使用 1 个值一次的算法，它可以使用 1 到 n 个值来对目标数字求和。
我在PHP中尝试了一些递归，但很快就用完了内存(50k值)，所以Python中的解决方案会有所帮助(时间/内存方面)。我很高兴在这里得到一些指导。
一个可能的解决方案是:找到所有可能的数字组合，以达到一个给定的总和
唯一的区别是，我需要在已经使用的元素上放置一个标志，这样它就不会被使用两次，并且我可以减少可能组合的数量
感谢任何愿意帮忙的人。
有很多方法可以思考这个问题。如果您执行递归，请确保首先确定您的最终情况，然后继续程序的其余部分。
这是我第一个想到的。
<?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]添加到其中，它仍然会小于或等于它---
完成最后一项（item[n]）后，查看您创建的子集-每个子集在其节点中都有其和，您可以看到哪些子集等于给定的和（哪些子集更小-您不再需要这些子集）。
正如我在开始时所写的那样，现在你需要弄清楚如何获得子集的最佳组合，这些子集之间没有共享成员。基本上，你会遇到一个类似于经典背包问题的问题，但有另一个限制（不是每一块石头都可以与其他石头一起使用）。也许这个限制真的有帮助，我不确定。
动态编程代替递归的基本思想是用占用内存空间来交换操作的冗余。我的意思是说，复杂问题的递归(通常是回溯背包式的问题，就像我们在这里遇到的一样)通常会多次计算相同的东西，因为不同的计算分支对彼此的操作和结果没有概念。动态编程保存结果，并在构建“更大”结果的过程中使用它们，依赖于先前的/“更小”的结果。因为堆栈的使用比递归简单得多，所以在维护函数的状态时，你不会遇到递归带来的内存问题，但是你需要处理大量的内存(有时你可以优化这一点)。
例如，在我们的问题中，尝试组合一个加起来等于所需总和的子集，以项目 A 开头的分支和以项目 B 开头的分支不知道彼此的操作。让我们假设项目 C 和项目 D 加起来等于总和，但它们中的任何一个单独添加到 A 或 B 都不会超过总和，并且 A 在解决方案中不与 B 一起（我们可以有 sum=10、A=B=4、C=D=5，并且没有总和等于 2 的子集（所以 A 和 B 不能在同一组中））。试图找出 A 的组的分支将（在尝试并拒绝在其组中包含 B 之后）添加 C（A C=9），然后添加 D，此时将拒绝该组和引用（A C D=14
注意：写这个答案时环顾四周，我遇到了一个我不熟悉的技术，可能对你来说是一个更好的解决方案：记忆。取自维基百科：
内存化是一种优化技术，主要用于存储昂贵的函数调用的结果，并在再次出现相同的输入时返回缓存的结果，从而加快计算机程序的速度。
