0

这是一个复杂的问题，所以请耐心等待。假设我有一个返回一组整数的查询。

2387
3357
3471
4885
5867
6170
8170
9777
12970
13190
17670
20470
160159

这些显而易见的一切对我来说都有意义，即使很难看出它们对你有什么作用。为方便起见，它们代表一种度量。现在我的第一个尝试是将特定的数据库值与通过上传过程获得的数字匹配在这种情况下，我想匹配37,174

现在，很明显，通过查看您可以看到没有一条记录与我正在寻找的数量相匹配。我真正的问题是，有没有办法查看某些金额的某种组合是否会达到我正在寻找的金额。我正在寻找最好能够滚动到 SQL 查询中的东西，但是我使用 C# 进行所有处理，所以如果我缺少可以利用的东西，请朝正确的方向轻推将不胜感激。我尝试了谷歌搜索，由于这个问题的措辞很微妙，我找不到任何相关/有用的东西。仍然是新手，所以我不知道 C# 中是否只有一个方法或一个类，或者 Postgres 的某些功能允许这样做。

编辑** 我知道如何使用循环来做到这一点，但我知道那将是一个糟糕的性能选择。

4

5 回答 5

1

在 SQL 中执行此操作的唯一方法是蛮力方法。例如，以下查询将考虑三个数字的所有组合：

select *
from t t1 join
     t t2
     on t1.val < t2.val join
     t.t3
     on t2.val < t3.val
where t1.val + t2.val + t3.val = 37174;

组合从最小值到最大值排序，没有重复。

如果您想要最接近您的目标的总和，那么您可以执行以下操作：

select 
from t t1 join
     t t2
     on t1.val < t2.val join
     t.t3
     on t2.val < t3.val
order by abs(t1.val + t2.val + t3.val - 37174)
limit 1;

如果您想要最多三个数字，则在列表中包含一个 0 值。

而且，所有这些都概括为固定数量的连接。

要做一个变量号，你需要使用递归查询。

对于这种类型的搜索，使用 SQL 比使用 C# 确实有一个优势。默认情况下，SQL 可以利用多线程并行性。

于 2013-05-29T16:02:23.287 回答
1

使用Combinatronics 库：

var values = new int[] { 1, 2, 3, 4, 5};
var target = 9;
var candidates = Enumerable.Range(1,values.Count())
                           .SelectMany(x => new Combinations<int>(values, x))
                           .Where(x => x.Sum() == target);

这将为您提供与您的目标值匹配的所有可能组合。如果您更喜欢第一个（使用FirstOrDefault()）或应用更多逻辑，这取决于您。

在您的示例中，没有组合加起来37174。

于 2013-05-29T16:15:30.370 回答
1

随着数字的增加，选项的数量呈指数增长。

例如：

如果你有三个数字，那么你必须检查 7 个组合

A, B, C, A+B, A+C, B+C, A+B+C

有四个，有

A, B, C, D, 
A+B, A+C, A+D, B+C, B+D, C+D,
A+B+C, A+B+D, A+C+D, B+C+D
A+B+C+D

等等。

所以我会说，不，没有简单的 SQL 方法可以绝对找到答案。

但是，您可以使用交叉连接来找到更简单的解决方案。

例如：如果您的表格t包含包含值的字段 i，则在结果中添加一个 0 数字并...

insert t (i)
select 0 union
select 2387 union
select 3357 union
select  3471 union
select  4885 union
select  5867 union
select  6170 union
select 8170 union
select  9777 union
select  12970 union
select  13190 union
select  17670 union
select  20470 union
select  160159

select *, t1.i + t2.i + t3.i + t4.i + t5.i + t6.i + t7.i
 from t t1
    cross join t t2 
    cross join t t3 
    cross join t t4 
    cross join t t5
    cross join t t6
    cross join t t7
where t1.i+t2.i+t3.i+t4.i+t5.i+t6.i+t7.i = 37174

哪个会给你组合......

2387    3471    4885    13190   4885    4885    3471

现在您可能有不允许重复的限制，在这种情况下，您的数据没有解决方案

于 2013-05-29T16:15:49.637 回答
1

尝试类似：

WITH RECURSIVE match(val, res) AS
(SELECT st.val , 1234 - st.val as res
 FROM your_table st
 WHERE 1234 - st.val >= 0
 UNION ALL
 SELECT nt.val,  match.res - nt.val 
 FROM your_table nt
 JOIN match ON match.res - nt.val >= 0
),

 final_match (val, res) AS
(SELECT match.val , match.res
 FROM match 
 WHERE match.res = 0
 UNION ALL
 SELECT match.val,  match.res
 FROM match
 JOIN final_match ON final_match.val = match.res
)

SELECT *
FROM final_match
ORDER BY res DESC;

这个想法 - 递归地构建所有数字组合，这可以导致你的总和。然后挑一个，有your_number - sum = 0

于 2013-05-29T16:19:55.217 回答
0

使用 SQL Server 语法 - 我不知道是否存在等效于递归 CTE 的 postgres

;with cte as
(
    select  cast(val as varchar(MAX)) as valtxt
    ,       val
    ,       val as summed
    from #temp

    union all
    select  C.valtxt +' + ' + CAST(C2.val as varchar(max))
    ,       C2.val
    ,       C.summed + C2.val
    from cte C
    inner join #temp C2
    on c.val < C2.val
    where C.summed <= 37174
)
select top 1 valtxt, summed from cte order by ABS(summed - 37174)

（其中#temp 是包含值的表）

于 2013-05-29T16:30:54.470 回答