2

我一直在使用 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 解决方案是可能的...

4

2 回答 2

1

这个问题与背包问题和子集​​和问题密切相关。

背包问题：给定一堆物品，每个物品都有一个重量和一个值，找到一个总重量低于某个目标且总价值最大的子集。您的问题可以被视为每个项目的重量和价值相等的变体。

子集和问题：给定一堆整数，找到一个和等于 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
于 2013-07-12T02:02:15.300 回答
0

不幸的是，子集和问题是 NP 完全的，因此您不太可能找到对较大输入表现良好的精确算法。存在一个近似算法（在文章中解释），它的运行时间取决于你需要多接近。如果您需要一个精确的解决方案，那么本文中描述的动态规划可能会胜过您当前的解决方案。

于 2013-07-11T23:56:01.333 回答