README

PHP SubsetSum 实现

给定一个目标数字和一个数字列表，确定哪些数字组合等于目标数字。

例如：以 25 作为目标数字，以 10、5、15 作为数字列表，这将确定 25 = 10 + 15。

要求

PHP >= 7.1
BCMath 扩展

安装

通过命令行使用 composer 需求此包

composer require mistralys/subsetsum

或直接编辑 composer.json

"require": 
{
    "mistralys/subsetsum": "dev-master"
}

用法

使用 create 方法创建一个新的实例，可用于检索匹配项或配置选项

$sub = SubsetSum::create(25, array(5,10,7,3,20));

检查是否存在匹配项

一些方法如 getShortestMatch() 可能返回 null，因此最好先检查是否存在匹配项。

if(!$sub->hasMatches())
{
    echo 'No matches.';
}

获取所有匹配项

检索所有匹配的数字组合

$matches = $sub->getMatches();

这将返回如下数组

array(
    array(3, 5, 7, 10),
    array(5, 20)
)

注意：每个匹配结果中的数字始终按升序排序。

获取最短匹配项

最短匹配项是使用最少数字组合的匹配项。

// check if there are matches, since the method can return null.
if($sub->hasMatches())
{
	$match = $sub->getShortestMatch();
}

在示例中，这将返回以下匹配数组

array(5, 20)

获取最长匹配项

最长匹配项是使用最多数字组合的匹配项。

// check if there are matches, since the method can return null.
if($sub->hasMatches())
{
	$match = $sub->getLongestMatch();
}

在示例中，这将返回以下匹配数组

array(3, 5, 7, 10)

调整小数位数和舍入

默认情况下，内部计算将数字四舍五入到 2 位小数，使用 PHP 的默认“四舍五入到半”舍入。这可以很容易地根据您的需要调整

// 4 decimals, default rounding mode
$sub->setPrecision(4);

// 1 decimal, specific rounding mode
$sub->setPrecision(1, PHP_ROUND_HALF_DOWN);

可能的完整模式列表可在此处找到

https://php.ac.cn/manual/en/math.constants.php

整数运算

在整数模式下工作只是意味着使用 0 的精度。

$sub->makeInteger();

注意：匹配数组将包含整数，但它们仍然被类型化为浮点数。您需要根据需要将它们强制转换为 int。

性能

请注意：计算子集和具有指数复杂性，随着要搜索的数字数量的增加而增加。您可以使用更大的集合轻松地将服务器拖垮，因此我建议在您的应用程序中设置数字数量的限制。

致谢

初始机制受 StackOverflow 上的此答案的启发

http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum/#answer-43351998

还有另一个比这更深入的有趣包

https://github.com/pipan/subsetsum-php

mistralys / subsetsum

维护者

详细信息