需要T-SQL查询查找所有可能的方法

Question

create table #sample (
    product varchar(100),
    Price float
) 

insert into #sample values ('Pen',10)
insert into #sample values ('DVD',29)
insert into #sample values ('Pendrive',45)
insert into #sample values ('Mouse',12.5)
insert into #sample values ('TV',49)

select * from #sample 

考虑以下情况…

我有1000美元，想购买以上列出的东西。

我想全部用完这笔钱。

因此，我需要一个查询来得知所有产品单位的总费用为1000美元。

有帮助吗？

- vignesh

---

你想在T-SQL中实现背包问题的解决方案吗？ - flup

不清楚您想知道用1000美元可以购买多少个每种产品，还是想知道用1000美元可以购买多少种及哪些组合的产品。 - Frazz

我可以用1000美元购买多少种不同的产品组合？应该是所有产品的混合。 - vignesh

还有其他限制吗？如果提供了100支笔或80部电影的解决方案，那是否有效？ - Richard Vivian

为什么价格是varchar类型？ - avb

错误地打了一下，如果你可以改变它的话... 没有具体的原因。 - vignesh

Answer 1

你所提到的问题也被称为背包问题。有一系列算法可以用来解决这个问题。最著名的是动态规划，它要求重量是整数，因此你需要以分为单位进行测量。其中任何一个都不容易在t-sql中实现。

我实际上找到了一个人在SQL Server中的实现链接：http://sqlinthewild.co.za/index.php/2011/02/22/and-now-for-a-completely-inappropriate-use-of-sql-server/ 请注意标题，他们也认为这是数据库的一种不适当使用方式。我建议您使用其他语言来解决这个问题。

- flup

---

我无法打开那个...它被重定向到其他地方了...它要求我上传图片..没有其他内容。 - vignesh

+1 我想@flup是正确的，不要在数据库中执行此操作 - 你可以使用CLR过程代替 http://msdn.microsoft.com/en-us/library/8bs2ecf4(v=vs.110).aspx - gotqn

@vignesh 不确定，这个链接在这里运行良好。但是重点是，即使这位作者在实现此功能时也认为 SQL 不是正确的方法。 - flup

@ gotqn 是的，如果这不是一个知识性练习，而且仍然要在 SQL Server 中保持绝对限制，那似乎是最好的方法。 - flup

+1 对于问题的历史注释。顺便感谢编辑。 :) - zx81

Answer 2

可以通过将当前项目的空间限制为未花费的资金来删除大量数据。

在我的家庭系统上，运行需要花费2.6秒至2.8秒的时间。在SQLFiddle上，前几次运行可能需要更长时间，然后稳定在1.8秒左右。

WITH Unit(N) AS (
  SELECT N
  FROM   (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) t(N)
), Counter(N) AS (
  SELECT u.n + 10*te.n + 100*hu.n
  FROM   Unit u CROSS JOIN Unit te CROSS JOIN Unit hu
  WHERE  u.n + 10*te.n + 100*hu.n <= (SELECT 1000 / Min(Price) FROM Sample))
SELECT N INTO #Counter FROM Counter;

WITH Products AS (
  SELECT [Pen], [DVD], [PenDrive], [Mouse], [TV]
  FROM   (SELECT product, price FROM sample) s PIVOT
         (MAX(price) FOR product IN ([Pen], [DVD], [PenDrive], [Mouse], [TV])) p
)
SELECT cP.N Pen, cD.N DVD, cPe.N PenDrive, cM.N Mouse
     , CAST((1000 - p.pen * cP.N - p.DVD * cD.N 
           - p.PenDrive * cPe.N - p.Mouse * cM.N) / p.TV as INT) TV
     , Money = p.pen * cP.N + p.DVD * cD.N + p.PenDrive * cPe.N
             + p.Mouse * cM.N 
             + p.TV * CAST((1000 - p.pen * cP.N - p.DVD * cD.N 
                          - p.PenDrive * cPe.N - p.Mouse * cM.N) / p.TV as INT)
From   Products p
       LEFT  Join #Counter cP ON cP.N  <= (1000 / p.Pen)
       LEFT  Join #Counter cD ON cD.N  <= ((1000 - p.pen * cP.N) / p.DVD)
       LEFT  Join #Counter cPe 
       ON cPe.N <= ((1000 - p.pen * cP.N - p.DVD * cD.N) / p.PenDrive)
       LEFT  Join #Counter cM 
       ON cM.N  <= ((1000 - p.pen * cP.N - p.DVD * cD.N
                   - p.PenDrive * cPe.N) / p.Mouse)
WHERE  p.pen * cP.N + p.DVD * cD.N
     + p.PenDrive * cPe.N + p.Mouse * cM.N 
     + p.TV * CAST((1000 - p.pen * cP.N - p.DVD * cD.N - p.PenDrive * cPe.N
                  - p.Mouse * cM.N) / p.TV as INT) = 1000

变更内容

• #Counter 现在是一个临时表，它只计算一次
• 各种产品 CTE 已经被替换为样本表旋转
  • 产品 CTE 中的 CROSS JOIN 已经消失，它们仍然存在于主查询中，但减少了四个 CROSS JOIN 总是好的
• TOP 已经消失，WHERE 条件负责仅显示完美解决方案
• 在主查询中，我们现在有 LEFT JOIN... 不对，它们仍然是 CROSS JOIN，LEFT JOIN 是用来限制行数的 ON 子句不存在的情况下使用的

工作原理
产品价格未旋转，使得可以通过“名称”（列名）获取产品价格。
FROM块的工作方式类似于4个缩进的FOR，其中（1000-已经花费）/价格子句将计数器限制在不超过1000美元的值上。
最后一个产品总是通过差异（剩余多少$ / 价格）计算，完全删除CROSS JOIN

SQLFiddle演示，总金额为1000美元。
根据提供的数据，有3531个解决方案。

---

旧回答

如果您想让服务器在您午餐的所有时间运行，这是一个愚蠢的解决方案。
请注意，此解决方案探索了问题的所有空间，因此性能最好也很差。

WITH Base(N) AS(
  SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
  SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
  SELECT 1 UNION ALL SELECT 1)
, Unit(N) AS (
  SELECT Row_Number() Over (ORDER BY (SELECT NULL)) - 1
  FROM   Base)
, Counter(N) AS (
  SELECT u.n + 10*te.n + 100*hu.n + 1000*th.n
  FROM   Unit u
         CROSS JOIN Unit te --tens
         CROSS JOIN Unit hu --hundreds
         CROSS JOIN Unit th --thousands
  WHERE  u.n + 10*te.n + 100*hu.n + 1000*th.n <= (SELECT 1000 / Min(Price) 
                                                  FROM Sample))
, Pens AS (
  SELECT product, Price = price * N, Quantity = N
  FROM   sample CROSS JOIN Counter
  WHERE  product = 'Pen' AND  N <= 1000 / Price)
, DVDs AS (
  SELECT product, Price = price * N, Quantity = N
  FROM   sample CROSS JOIN Counter
  WHERE  product = 'DVD' AND  N <= 1000 / Price)
, Pendrives AS (
  SELECT product, Price = price * N, Quantity = N
  FROM   sample CROSS JOIN Counter
  WHERE  product = 'Pendrive' AND  N <= 1000 / Price)
, Mouses AS (
  SELECT product, Price = price * N, Quantity = N
  FROM   sample CROSS JOIN Counter
  WHERE  product = 'Mouse' AND  N <= 1000 / Price)
, TVs AS (
  SELECT product, Price = price * N, Quantity = N
  FROM   sample CROSS JOIN Counter
  WHERE  product = 'TV' AND  N <= 1000 / Price
  )
SELECT TOP 10
       Pen = p.Quantity
     , DVD = d.Quantity
     , Pendrive = pe.Quantity
     , Mouse = m.Quantity
     , TV = t.Quantity
     , Price = p.Price + d.price + pe.price + m.price + t.price
FROM   pens p
       CROSS JOIN DVDs d
       CROSS JOIN Pendrives pe
       CROSS JOIN Mouses m
       CROSS JOIN TVs t
WHERE  p.Price + d.price + pe.price + m.price + t.price <= 1000
ORDER BY p.Price + d.price + pe.price + m.price + t.price DESC

SQLFiddle演示，总金额为100美元（运行大约需要2秒钟）
SQLFiddle演示，总金额为200美元（运行大约需要6秒钟）
1000美元的演示可能会导致超时

工作原理

• Base用作Unit的基础。
• Unit从0到9计数
• Counter使用Unit从0到9999计数，或者根据您想花费的更便宜物品的价格除以价格所施加的限制。
• 每个项目都有自己的CTE来计算该项目在您的资本内任意次数的价格。
• 产品CTE交叉连接以检查货币限制内的每种组合。
• TOP 10在这里是因为可能会有多个组合使用了完全相同的金额。

只是说，是的，你可以在SQLServer中设计解决方案，这甚至不难，但这并不意味着你应该这样做。

- Serpiton

Answer 3

如果我正确理解问题陈述，那么这是一个非常简单的查询：

select product, price, floor(1000 / price) as QtyToBuy

- Metaphor

---

这是针对单个产品的问题。我想知道用1000美元可以购买多少种组合的产品。 - vignesh

您可能需要修改问题以澄清这一点。单词“组合”应该在其中出现。 - Metaphor

Answer 4

这是硬编码的，灵活性很小。我的系统运行了2分钟。但可能会有所帮助，如果不是的话，我很抱歉。fnGenerate_Numbers是一个表函数，返回参数范围内的整数。如何实现这个功能。

DECLARE @Max INT,
        @Pens money,
        @Dvds money,
        @Pendrives money,
        @Mouses money,
        @Tvs money

SELECT @Max = 1000,
       @Pens = 10,
       @Dvds = 29,
       @Pendrives = 45,
       @Mouses = 12.5,
       @Tvs = 49    


;WITH Results AS
(
    SELECT p.n pens, d.n dvds, pd.n pendrives, m.n mouses, t.n tvs, tot.cost
    FROM fnGenerate_Numbers(0, @Max/@Pens) p -- Pens
        CROSS JOIN fnGenerate_Numbers(0, @Max/@Dvds) d -- DVDs
        CROSS JOIN fnGenerate_Numbers(0, @Max/@Pendrives) pd -- Pendrives
        CROSS JOIN fnGenerate_Numbers(0, @Max/@Mouses) m -- Mouses
        CROSS JOIN fnGenerate_Numbers(0, @Max/@Tvs) t -- Tvs
        CROSS APPLY (SELECT p.n * @Pens + d.n * @Dvds + pd.n * + @Pendrives + m.n * @Mouses + t.n * @Tvs cost) tot
    WHERE tot.cost < @Max
), MaxResults AS
(
    SELECT 
        MAX(pens) pens,
        dvds,
        pendrives,
        mouses,
        tvs
    FROM Results
    GROUP BY
        dvds,
        pendrives,
        mouses,
        tvs
)
SELECT mr.*, r.cost FROM MaxResults mr
    INNER JOIN Results r ON mr.pens = r.pens 
        AND mr.dvds = r.dvds
        AND mr.pendrives = r.pendrives
        AND mr.mouses = r.mouses
        AND mr.tvs = r.tvs
ORDER BY cost

- EarlOfEnnui