sql - 如何将项目子集的总和与目标数字相匹配？

Question

我一直在 SQL Server 2008 R2 中开发一个可以匹配拆分数量的存储过程。我的算法有问题；我开发的那个，我将描述，不能超过 55 个项目。如果有替代解决方案可用，则算法名称即可。我可以实现它。

问题:

我有一个数量列表，这些数字的某些子集的总和需要等于目标数字。数量不是唯一的。例如，假设您有数量:

1, 2, 3, 8

目标数量为11。存在两种解法:1+2+8和3+8。找到哪个解决方案并不重要，我只需要一个解决方案。

这就是我试图解决它的方法(请记住，这是在 SQL 中)。为每个数量分配一个位掩码:

1:  0001
2:  0010
3:  0100
8:  1000

使用从 15 到 1 的计数器并使用按位与，我们得到:

15:  1111: 1, 2, 3, 8     total: 14
14:  1110: 2, 3, 8        total: 13
13:  1101: 1, 2, 8        total: 11 (solution found)
...
2:   0010: 2
1:   0001: 1

这很好用...当项目数少于 56 时。此时，2^57 会被截断。我使用 decimal(38,0) 作为我的数据类型，所以我有 17 个字节(136 位)。我几乎可以保证永远不会拥有超过 125 个项目，所以这很好。但是在 57 岁时，我的位掩码策略失败了。

这有意义吗？如果我需要澄清算法，请发表评论。

问题 1: 这个算法可以横向扩展到 125 吗？如果没有，或者其他解决方案会更有效:

问题 2:我可以实现以解决该问题的另一种算法的名称是什么？当然，这类问题很常见，它有一个命名算法……对吧？

我的实现，对于那些感兴趣的人

取消注释foo的创建和填充以创建测试数据。

--create table foo
--(
--  ID          int         primary key identity(1,1),
--  Qty         int         not null
--)
--go

--create nonclustered index IX_FOO__Qty on foo (Qty) include (ID)
--go

--insert into foo (Qty) values (1)
--insert into foo (Qty) values (1)
--insert into foo (Qty) values (2)
--insert into foo (Qty) values (3)
--insert into foo (Qty) values (7)

declare @seek int = 9,
        @total int = 0,
        @n int,
        @oldn int = 0,
        @i int

select @i = SQUARE(count(1))-1 from foo     -- start counting down from the top

select 
    x.ID, 
    x.Qty, 
    x.v as flags, 
    0 isanswer,
    convert(varbinary(16), v) hex
into #tmp
from
(
    select f.ID, f.Qty, POWER(2, row_number() over(order by f.qty) - 1) v
    from foo f
) x

while @i > 0
begin
    select @total = sum(Qty), @n = count(ID) from #tmp t where flags & @i != 0

    if (@total = @seek and @oldn < @n)
    begin
        update #tmp set isanswer = case when flags & @i != 0 then 1 else 0 end
        select @oldn = @n
    end

    select @i = @i - 1
end


select * from #tmp where isanswer = 1
drop table #tmp

这有结果集:

ID  Qty     flags   isanswer   hex
1   1       1       1          0x00000001
2   1       2       1          0x00000002
5   7       16      1          0x00000010

有什么想法吗？我知道我在 C# 中做这件事会容易得多，但如果 SQL 解决方案是可能的......

Answer 1

这个问题与knapsack problem密切相关和 subset sum problem .

背包问题:给定一堆元素，每个元素都有一个重量和一个值，找到一个子集，其总重量低于某个目标且总值(value)最大。您的问题可以看作是每个项目的重量和值(value)相等的变体。

子集求和问题:给定一堆整数，找到一个和等于 0(或其他目标值)的非空子集。您的问题可以被视为一个变体，增加了所有整数都是正数的限制。

仅从项目数量的角度来看，这两个问题都是 NP 完全问题。这意味着通常解决问题所需的时间是元素数​​量的指数。

但是，如果目标值受到限制，则有一个动态规划解决方案是 O(N*T)，其中 N 是元素的数量，T 是目标。所以当有125个元素时只要目标值不是很大就可以解决问题。

这是伪代码中的算法:

function solve(quantities, target):

    possible[0 .. target+1] = array of booleans initialized to False
    choices[0 .. target+1] = array of IDs

    possible[0] = True

    -- compute solutions to all subproblems
    for each id:
        v = quantities[id]
        -- try to add v to all existing solutions
        for i = target down to v:
            if possible[i - v] and not possible[i]:
                possible[i] = True
                choices[i] = id

    if not possible[target]:
        fail

    -- backtrack to get the full solution
    soln = []
    while target != 0:
        id = choices[target]
        soln.append(id)
        target = target - quantities[id]
    return soln