这里有一个包含内容的表格
ID Qty
----------
1 2
2 4
3 1
4 5
现在，如果我必须选择行使得Qty的总和等于10，我该怎么做？
例如：2+4+1=7，但是如果加上5则为12。
所以忽略2，则4+1+5=10。
我该如何实现这个功能？
编辑：
我想要任何可能的组合，使其总和达到给定值。比如说，如果是7，则任何行的总和都可以是7；同样地，如果是8，则任何行的总和都可以是8。
需要找到组合等于给定值的行/行。
如何获取行的总和等于给定值的数据
8
现在，如果我必须选择行使得Qty的总和等于10，我该怎么做？
例如：2+4+1=7，但是如果加上5则为12。
所以忽略2，则4+1+5=10。
我该如何实现这个功能？
编辑：
我想要任何可能的组合，使其总和达到给定值。比如说，如果是7，则任何行的总和都可以是7；同样地，如果是8，则任何行的总和都可以是8。
需要找到组合等于给定值的行/行。
- Humdum
4
你想要相加多少个数字？总是三个吗？ - gbn
会只有一个解决方案吗？如果有多个可能的解决方案，您是想要所有选项还是只是第一个遇到的？ - Chris Gill
你能解释一下你需要这个东西的原因吗？也许有其他方法可以实现你所描述的需求。 - Andrew Savinykh
让SQL Server在合理的时间内解决NP完全问题是不太可能发生的。 - Damien_The_Unbeliever
4个回答
3
如果您希望始终是三个数字加起来等于10，那么这样做：
SELECT
*
FROM
MyTable t1
JOIN
MyTable t2 ON t1.ID <> t2.ID
JOIN
MyTable t3 ON t1.ID <> t3.ID AND t2.ID <> t3.ID
WHERE
t1.Qty + t2.Qty + t3.Qty = 10
如果您需要2、4或5个数字，则无法在SQL中实现
编辑：
- 更新以按ID而非数量忽略
- 再次强调：如果您需要2、4或5个数字，则无法在SQL中实现
- gbn
4
1不一定是三个数字，它们可以是任何组合，我想要那些行的总和等于用户传递的数字。 - Humdum
你可以编写一个存储过程，动态地编写上述存储过程以添加(n)个条目并执行它。从1个条目开始，检查是否返回任何行。如果没有行，则动态生成2个条目的SQL。迭代到表中的行数。如果有多个解决方案来求和(n)项，不确定你会做什么。 - Chris Gill
@Humdum：除非您指定一个上限，否则在SQL中确实不太实用。 - gbn
@balexandre: 我不能在工作中访问 Pastebin，所以今晚我将尝试更多的行数… - gbn
2
当你在SQL中处理这样的任务时，你需要使用游标方法。
游标允许你逐行进行操作，这正是你所需要的，例如：
- 你想要将总和为10的分组
这些是任务：
- 将所有表格选择到一个临时表
#TBL_ALL中 - 逐行循环，当行总和达到10时，从临时表中删除并插入到最终临时表
#TBL_FINAL中 - 重复以上步骤，直到无法执行
#TBL_ALL总和
一个例子：
测试表：
/****** Object: Table [dbo].[tblExample] Script Date: 06/09/2011 11:25:27 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[tblExample](
[Id] [int] IDENTITY(1,1) NOT NULL,
[Qty] [int] NOT NULL,
CONSTRAINT [PK_tblExample] PRIMARY KEY CLUSTERED
(
[Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
测试数据：
INSERT INTO tblExample SELECT 2;
INSERT INTO tblExample SELECT 4;
INSERT INTO tblExample SELECT 1;
INSERT INTO tblExample SELECT 5;
INSERT INTO tblExample SELECT 5;
INSERT INTO tblExample SELECT 11;
INSERT INTO tblExample SELECT 1;
INSERT INTO tblExample SELECT 2;
INSERT INTO tblExample SELECT 3;
INSERT INTO tblExample SELECT 4;
INSERT INTO tblExample SELECT 7;
INSERT INTO tblExample SELECT 9;
INSERT INTO tblExample SELECT 1;
INSERT INTO tblExample SELECT 2;
存储过程：
分组表格：
ids qty group
12 9 1
7 1 1
11 7 2
9 3 2
4 5 3
5 5 3
2 4 4
10 4 4
14 2 4
未使用的数字：
id qty
1 2
8 2
3 1
13 1
6 11
希望这有所帮助。
对于无法访问PasteBin的用户，这是SP。
CREATE PROCEDURE getGroups
(
@groupByQty int, -- grouping number
@numberRuns int -- how many loops
-- usage: getGroups 10, 10
)
AS
SET NOCOUNT ON;
-- declare all variables
DECLARE @rowId int,
@rowQty int,
@rowTotal int,
@groupId int,
@totalRuns int,
@continue bit
-- set up our final temporary table
CREATE TABLE #TBL_COUNT
(
ids NVARCHAR(4000),
qty int,
[group] int
)
-- initializate variable
SET @groupId = 1;
SET @continue = 1;
SET @totalRuns = 0;
SELECT Id, Qty INTO #TBL_ALL FROM tblExample ORDER BY Qty DESC;
WHILE @totalRuns <= @numberRuns
BEGIN
-- declare the cursor
DECLARE Product CURSOR FOR SELECT Id, Qty FROM #TBL_ALL ORDER BY Qty DESC;
OPEN Product;
FETCH Product INTO @rowId, @rowQty;
PRINT ' ';
PRINT '### Run: ' + CAST(@totalRuns AS nvarchar(10)) + ' #################################################################';
PRINT 'Grouping Table by ' + CAST(@groupByQty AS nvarchar(10)) + ' | group id = ' + CAST(@groupId AS nvarchar(10));
-- Retrieve and process the first row
SELECT Top 1 @rowId = Id, @rowQty = Qty FROM #TBL_ALL ORDER BY Qty DESC;
PRINT 'First Row: id = ' + CAST(@rowId AS nvarchar(10)) + ' | qty = ' + CAST(@rowQty AS nvarchar(10));
-- sum it up and see if we have @groupByQty
SELECT @rowTotal = ISNULL(SUM(qty),0) FROM #TBL_COUNT WHERE [group] = @groupId;
PRINT 'Current sum in #TBL_COUNT: @groupId = '+ CAST(@groupId AS nvarchar(10)) +' | @rowTotal = ' + CAST(@rowTotal AS nvarchar(10)) + ' | (@rowTotal + @rowQty) = ' + CAST((@rowTotal + @rowQty) AS nvarchar(10));
IF @rowQty > @groupByQty
BEGIN
PRINT ' x First row has an unused number';
END
ELSE
BEGIN
-- handle result
IF (@rowTotal + @rowQty) = @groupByQty
BEGIN
PRINT '+++ Current sum is ' + CAST(@groupByQty AS nvarchar(10)) + ' +++';
-- save number
INSERT INTO #TBL_COUNT SELECT @rowId, @rowQty, @groupId;
PRINT '### Inserted final # into #TBL_COUNT : id = ' + CAST(@rowId AS nvarchar(10)) + ' | qty = ' + CAST(@rowQty AS nvarchar(10)) + ' | group = ' + CAST(@groupId AS nvarchar(10));
-- remove from table as we use it already
DELETE FROM #TBL_ALL WHERE Id = @rowId;
-- we got 10, let's change our Groupping
SET @groupId = (@groupId + 1);
PRINT 'New group id: ' + CAST(@groupId AS nvarchar(10));
END
ELSE
BEGIN
IF (@rowTotal + @rowQty) < @groupByQty
BEGIN
PRINT '### Inserted into #TBL_COUNT : id = ' + CAST(@rowId AS nvarchar(10)) + ' | qty = ' + CAST(@rowQty AS nvarchar(10)) + ' | group = ' + CAST(@groupId AS nvarchar(10));
-- save number
INSERT INTO #TBL_COUNT SELECT @rowId, @rowQty, @groupId;
-- remove from table as we use it already
DELETE FROM #TBL_ALL WHERE Id = @rowId;
END
ELSE
BEGIN
PRINT ' x Unmatch number, will handle this latter';
END
END
END
-- start the main processing loop
WHILE @@Fetch_Status = 0
BEGIN
FETCH Product INTO @rowId, @rowQty;
PRINT '@@Fetch_Status = ' + CAST(@@Fetch_Status AS nvarchar(100));
IF @@Fetch_Status < 0
BEGIN
BREAK
END
-- we have the values of our row, let's use them
PRINT 'Fetched Row: id = ' + CAST(@rowId AS nvarchar(10)) + ' | qty = ' + CAST(@rowQty AS nvarchar(10));
-- sum it up and see if we have @groupByQty
SELECT @rowTotal = ISNULL(SUM(qty),0) FROM #TBL_COUNT WHERE [group] = @groupId;
PRINT 'Current sum in #TBL_COUNT: @groupId = '+ CAST(@groupId AS nvarchar(10)) +' | @rowTotal = ' + CAST(@rowTotal AS nvarchar(10)) + ' | (@rowTotal + @rowQty) = ' + CAST((@rowTotal + @rowQty) AS nvarchar(10));
-- handle result
IF (@rowTotal + @rowQty) = @groupByQty
BEGIN
PRINT '+++ Current sum is ' + CAST(@groupByQty AS nvarchar(10)) + ' +++';
-- save number
INSERT INTO #TBL_COUNT SELECT @rowId, @rowQty, @groupId;
PRINT '### Inserted final # into #TBL_COUNT : id = ' + CAST(@rowId AS nvarchar(10)) + ' | qty = ' + CAST(@rowQty AS nvarchar(10)) + ' | group = ' + CAST(@groupId AS nvarchar(10));
-- remove from table as we use it already
DELETE FROM #TBL_ALL WHERE Id = @rowId;
-- we got 10, let's change our Groupping
SET @groupId = (@groupId + 1);
PRINT 'New group id: ' + CAST(@groupId AS nvarchar(10));
-- start again
BREAK;
END
ELSE
BEGIN
IF (@rowTotal + @rowQty) < @groupByQty
BEGIN
PRINT '### Inserted into #TBL_COUNT : id = ' + CAST(@rowId AS nvarchar(10)) + ' | qty = ' + CAST(@rowQty AS nvarchar(10)) + ' | group = ' + CAST(@groupId AS nvarchar(10));
-- save number
INSERT INTO #TBL_COUNT SELECT @rowId, @rowQty, @groupId;
-- remove from table as we use it already
DELETE FROM #TBL_ALL WHERE Id = @rowId;
END
ELSE
BEGIN
PRINT ' x Unmatch number, will handle this latter';
END
END
END -- END WHILE @@Fetch_Status = 0
SET @totalRuns = @totalRuns + 1;
-- Close and dealocate
CLOSE Product;
DEALLOCATE Product;
END -- END WHILE totalRuns <= @numberRuns
-- let's sum our last group and remove it if it's not @groupByQty
SELECT @rowTotal = ISNULL(SUM(qty),0) FROM #TBL_COUNT WHERE [group] = @groupId;
IF @rowTotal <> @groupByQty
BEGIN
SET IDENTITY_INSERT #TBL_ALL ON
INSERT INTO #TBL_ALL (Id, Qty) SELECT Ids, Qty FROM #TBL_COUNT WHERE [group] = @groupId;
DELETE FROM #TBL_COUNT WHERE [group] = @groupId;
END
SET NOCOUNT OFF;
-- Show and Delete temp tables
SELECT * FROM #TBL_COUNT;
SELECT * FROM #TBL_ALL;
DROP TABLE #TBL_COUNT;
DROP TABLE #TBL_ALL;
注意: 我不是SQL专业人士，如果我做了什么奇怪的事情，请谅解。请记住，这是一种性能浪费的方法，也许有人可以在没有游标的情况下使用循环，点击此处查看更多信息
- balexandre
4
我不完全理解这段代码，但我有点怀疑它在一般情况下是否能正常工作，因为它似乎使用了贪婪策略，这可能会导致它做出错误的决定（并且因为它似乎是一个多项式时间算法，而子集求和问题是NP完全的）。例如，它是否正确处理以下数字序列（期望和为10）：2、7、5、3？ - Martin B
尝试自己操作，打开数据库，创建表格，插入数据并运行存储过程。虽然我没有花太多时间在这上面，但是这是可行的。对于你的例子：是的，因为它按
qty排序，所以数字将是7、5、3、2：处理中：保留7；7+5>10=卸载5；7+3=10->复制到临时文件；0+2<10->保留2；循环；2+5<10->保留5；结束；如果总和不等于10，则删除最后一组。 - balexandre我错过了关于排序的部分...但我仍然认为“贪婪算法”可能会产生不良影响。再举个例子，比如这个序列（仍然是期望和为10）：5、4、4、2？据我理解该算法，它将选择并保留5和4（因为它们的总和仍然小于10），然后拒绝其他的4和2，因为它们都会导致总和溢出... - Martin B
你说得对，现在这样不行，但我可以轻松地改变流程以排除“5”并继续处理第二个数字等等。我认为这是一个简单的任务。再说了，我不是SQL专家。 - balexandre
-1
如果您一直添加3个数字，就像GBN所说的那样，如果不是，则必须检查每行的每种组合，这将给您2到行数幂次方的组合，并且我不知道如何在一个查询中使用SQL完成它。如果您在SQL中使用循环，当然可以实现，但您应该找到一些好的算法来完成此任务。
- Piotr Auguscik
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接