Need T-SQL Query find all possible ways

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 

Consider this situation ...

I have 1000$, I want to buy something listed above.

I want to spend the entire amount

So I need a query which gives how much units in all products will cost 1000$

Any help ?

Answer 1

It's possible to remove a lot of data by limiting the space for the current item to the money not already spent.

On my home system it takes between 2600 ms and 2800 ms to run.
On SQLFiddle the first few runs can take more, then it stabilize around 1800ms.

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

What's changed

• The #Counter is now a temp table, it's calculated only once
• The various Product CTEs are gone, substituted by the sample table pivoted
  • The CROSS JOIN in the Products CTE are gone, they remain in the main select but four less CROSS JOIN is always good
• The TOP is gone, the WHERE contition takes care of showing only the perfect solutions
• In the main select we have now LEFT JOIN... nope they are still CROSS JOIN, the LEFT JOIN are used because the CROSS JOIN don't have the ON clause used to limit the number of rows

How it works
The products price unpivoted make it possible to get the products price by 'name' (column name).
The FROM block works like 4 indented FOR, where the (1000 - already spent) / price clauses, limit the counters only to the values that will not exceed the 1000$.
The last product is always calculated by difference (how many $ are still unspent / price), dropping a CROSS JOIN completely

SQLFiddle Demo with 1000$ as the total money.
With the data provided there are 3531 solution

---

Old Answer

If you want to have you server run for all the time of you lunch here is a dumb solution.
Mind you, this solution explore all the space of the problem so the performance will be, at best, crappy.

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 Demo with 100$ as the total money (it takes about 2 second to run)
SQLFiddle Demo with 200$ as the total money (it takes about 6 second to run)
A demo with 1000$ will probably result in a time-out

How this work

• Base serve as base of Unit.
• Unit count from 0 to 9
• Counter use Unit to count from 0 to 9999, or the limit imposed from by the cheaper money you want to spend divided by the price of the cheaper item.
• Every item has his CTE to calculate the price of that item for any number of times within your capital.
• The product CTEs are cross joined to check every combination within the limit of the money.
• The TOP 10 is here because there can be more then one combination where the exact amount of money is used.

That just to say that yes you can devise a solution in SQLServer, it's not even that difficult, but that doesn't mean that you should to it.

Answer 2

The problem you are referring to is also known as the knapsack problem. There's a range of algorithms you can use to solve this. The most well known is dynamic programming, it requires that the weights are integer numbers, so you'd have to measure in cents. None of them are easy to implement in t-sql.

I actually found a link to someone's implementation in sql server: http://sqlinthewild.co.za/index.php/2011/02/22/and-now-for-a-completely-inappropriate-use-of-sql-server/

Notice the title, they too find it an inappropriate use of a database. I'd recommend that you solve this in a different language.

Answer 3

If I understand the problem statement correctly, then it's a pretty simple query:

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

Answer 4

This is hard coded and has little flexiblity. Took my system 2 minutes to run. But might be helpful, sorry if it isn't. fnGenerate_Numbers is a table function that returns integers within the range of the parameters. Ways to do that.

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