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 2.6s and 2.8s to run.
On SQLFiddle the first few runs can take more, then it stabilize around 1.8s.
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 condition 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.
https://stackoverflow.com/questions/23166486
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian