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

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.