Results 1 to 10 of 10
  1. #1
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10

    Unanswered: SQL Challenge: Numeric Combinations

    I've been working with some interesting data puzzles recently and it got me thinking of some little challenges to try and solve in T-SQL.

    So here's one:
    Code:
    DECLARE @x table (
       id    int
     , price money
    )
    
    INSERT INTO @x (id, price)
      VALUES (1, 1.0)
           , (2, 1.0)
           , (3, 1.0)
           , (4, 1.5)
           , (5, 1.5)
           , (6, 2.0)
           , (7, 2.5)
           , (8, 2.5)
           , (9, 3.5)
    
    DECLARE @target money = 3.0
    
    /*
      Aim: find all combinations of items that when
           added together equal the target amount.
    
      Expected results if @target = 2.5:
           1, 4
           1, 5
           2, 4
           2, 5
           3, 4
           3, 5
           7
           8
    
      Expected results if @target = 3.0:
           1, 2, 3
           1, 6
           2, 6
           3, 6
           4, 5
    
      Expected results if @target = 3.5:
           1, 2, 4
           1, 3, 4
           2, 3, 4
           1, 2, 5
           1, 3, 5
           2, 3, 5
           4, 6
           5, 6
           1, 7
           1, 8
           2, 7
           2, 8
           3, 7
           3, 8
           9
    */
    I'm stumped on how to approach this one, any ideas?

    Good luck!
    George
    Home | Blog

  2. #2
    Join Date
    Jan 2013
    Posts
    354
    Provided Answers: 1

    NP-complete knapsack problem

    This is called a knapsack problem and it is known to be NP-complete. You are dead before you start. A procedural program with a greedy algorithm that halts on the first result actually does pretty good.

    The classic book on this is available as a free download:

    Operation Research

    The FORTRAN is awful and unstructured, but usable with lots of effort.

    My trick for small sets of (n) items in SQL was a table of {0, 1} in (n) and use a cross join to generate all possible combinations and their total. The other trick for larger values of (n) is to do (n-k) and discard the subset that overflowed. Take the candidates and add another column for the (n-k-1) case, repeat until you hit (n-k-k) columns. Brute force, plain and simple.

  3. #3
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Thanks Joe, I will give that a read.

    I'm kind of glad that it's not just me that can't solve it - I was starting to doubt my ninja-SQL skills!

    It is a reasonably trivial problem I had to keep working out in my head and on paper on some data analysis stuff over the last week and just assumed there would be a much cleverer way that I hadn't thought of
    George
    Home | Blog

  4. #4
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    ...and if Price can be negative, the problem gets even worse.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  5. #5
    Join Date
    Nov 2003
    Posts
    2,933
    Provided Answers: 12
    I do have a solution using a recursive query:

    Table setup:
    Code:
    create table x 
    (
       id    int not null primary key,
       price numeric(12,4) not null
    );
    
    INSERT INTO x
      (id, price)
    VALUES
      (1, 1.0),
      (2, 1.0),
      (3, 1.0),
      (4, 1.5),
      (5, 1.5),
      (6, 2.0),
      (7, 2.5),
      (8, 2.5),
      (9, 3.5);
    The actual query:
    Code:
    with calc as (
       select id as id, 
              cast(id as varchar(max)) as id_list, 
              cast(price as numeric(14,2)) as price
       from x
       where price <= 2
                             
       union all
                             
       select c.id, 
              p.id_list+','+ cast(c.id as varchar(max)),
              cast((c.price + p.price) as numeric(14,2))
       from x as c
         join calc as p on p.id < c.id
       where c.price + p.price <= 2
    )
    select *
    from calc
    where price = 2
    order by id_list
    The base query calculates more combinations than are actually needed.
    Limiting the values inside the CTE to less than the max. amount is an attempt to make it a bit more efficient.

    I don't expect this to scale very well though.

    Here is a SQLFiddle to play around with: http://sqlfiddle.com/#!6/77530/11
    Last edited by shammat; 04-09-13 at 14:21. Reason: Replaced Postgres only solution (using arrays) with SQL Server solution using a varchar
    I will not read nor answer questions where the SQL code is messy and not formatted properly using [code] tags: http://www.dbforums.com/misc.php?do=bbcode#code

    Tips for good questions:

    http://tkyte.blogspot.de/2005/06/how...questions.html
    http://wiki.postgresql.org/wiki/SlowQueryQuestions
    http://catb.org/esr/faqs/smart-questions.html

  6. #6
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    First off... sqlfiddle: GENUIS!
    I have used jsfiddle before but never knew an SQL equivalent existed! Bookmarked and signed up 8)

    Secondly.... that looks lovely!
    Very similar to something I tried earlier but I didn't wrap my head around the join criteria (and the following WHERE clause).

    Will give it a proper looksie tomorrow
    George
    Home | Blog

  7. #7
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    Quote Originally Posted by shammat View Post
    Limiting the values inside the CTE to less than the max. amount is an attempt to make it a bit more efficient.
    ...which is where negative prices would really gum things up.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  8. #8
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Luckily, for my real-world requirements, there is no negative (or zero) pricing





    Because it's not actually prices I'm dealing with, but it just seemed like an easier to explain scenario
    George
    Home | Blog

  9. #9
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    I thought this was just a "puzzle" George.
    Wait, this isn't a homework assignment is it?
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  10. #10
    Join Date
    Jan 2013
    Posts
    354
    Provided Answers: 1

    Actually, I did a puzzle like this ..

    The Best Sub-Array Problem


    Use a one-dimensional array, slots[1:n], and we want to find a sub-array, slots [a:b] , where (1 <= a <= b <= n) and SUM (slots [a:b]) is a maximum.

    If all the slots are positive or zero, then the sum of the whole array is the answer. Problem solved! But negative numbers make problems:
    1
    1
    -5
    1
    1

    The total for all five slots is -1, so that does not work. The best sub-arrays are slots[1:2] and slots [4:5] , so a simple total summation will not work.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •