php - 谜题 : How To Group Rows By A Particular Sum of a Particular Column

Question

如何将以下行分成 3 组，其中“美元”总和为 10。所有行都必须使用，且不得超过一次。

row|dollars
1|1
2|1
3|1
4|1
5|1
6|1
7|3
8|4
9|7
10|10

一个(许多可能的)期望结果是......

Row Group 1 = 10
Row Group 2 = 7,9
Row Group 3 = 1,2,3,4,5,6,8

额外积分:当从数学上不可能让每组的总和恰好达到 10 美元时，是否有一个公式可以让我们最接近这个值？

我虽然可能“HAVING sum(dollar) = 10 ”，或者，对于一个接近的解决方案，只需将一行排序并分配给一组，但这并没有让我接近。

Group Row By Sum of Specific Column equal to Specific Value有点涉及到这一点，但是，假设它们可能有数百万行，就会出现性能问题。我被难住了。

如果有帮助的话，我正在使用 php 和 mysql。纯 sql 解决方案是理想的，但某种组合也很棒。感谢您的任何建议。

编辑:如果我不清楚，我想返回使这成为可能的行，而不仅仅是“分组依据”它们。

Answer 1

我认为你不能只用 sql 来做到这一点，但它肯定会有所帮助。我首先进行像 select * from data where dollars <= 10 order by dollars desc 这样的查询然后在 php 中创建一个算法，遍历结果并将美元相加，直到找到三组加起来为 10 的数字。

它会开始从大到小相加，直到找到正确的总和，然后存储它，从列表中删除这些项目，然后重新开始，共三次。我正在使用手机，但当我使用计算机时，我会用一个工作示例更新答案。

编辑:到达我的电脑。这是非常困惑的代码，但它应该引导您走向正确的方向。

$dataset = [10,7,4,3,1,1,1,1,1,1];
$results = [];

function add_to_ten(&$data) {
    $sum = 0;
    $results = [];

    foreach ($data as $index => &$datum) {
        if ($datum == 0) {
            continue;
        }
        if ($sum + $datum <= 10) {
            $sum += $datum;
            $results[] = $index;
            $datum = 0;
        }
        if ($sum == 10) {
            return $results;
        }
    }
}

print_r(add_to_ten($dataset));
print_r(add_to_ten($dataset));
print_r(add_to_ten($dataset));