THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Peter Larsson

Thinking outside the box

Another bin-packaging algorithm using recursion and XML

This time I will show you an algorithm to do the dreaded bin-packaging using recursion and XML.
First, create some sample data like this

-- Prepare sample data
DECLARE @Sample TABLE
        (
            RowID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
            Expense SMALLMONEY NOT NULL
        )
 
-- Populate sample data
INSERT  @Sample
        (
            Expense
        )
VALUES  (12.51),
        (45.63),
        (66.35),
        (92.66),
        (65.46),
        (54.01),
        (32.23),
        (27.16),
        (78.92),
        (14.58)
 
Next, we need to create a variable to hold the user's wanted total sum.

-- Prepare user supplied parameter
DECLARE @WantedSUM SMALLMONEY = 111.09

And we also need to create a temporary staging table to hold the valid combinations
 
-- Prepare temporary staging table
DECLARE @Temp TABLE
        (
            CombID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
            TrackPath XML NOT NULL
        )

Now we only have to do the calculations!
Here I am using a special trick to get the unique combination, since the path of records 1>2>3 is the same as 1>3>2, 2>1>3, 2>3>1, 3>1>2 and 3>2>1. See explanation between combination and permutation at Wikipedia here.
To keep track of which records I already have used in the total sum, I simply remove the record id (RowID) from the Hits list.
And, to give the correct answer at the end, I build a XML string with visited RowID's building up the correct sum.
 
-- Calculate all possible permutations using recursion
;WITH ctePack(Total, Hits, TrackPath)
AS (
        SELECT  s.Expense AS Total,
                (SELECT '#' + CAST(x.RowID AS VARCHAR(MAX)) FROM @Sample AS x WHERE x.RowID <> s.RowID ORDER BY x.RowID FOR XML PATH('')) + '#' AS Hits,
                '<ID>' + CAST(s.RowID AS VARCHAR(MAX)) + '</ID>' AS TrackPath
        FROM    @Sample AS s
        WHERE   s.Expense <= @WantedSum
 
        UNION ALL
 
        SELECT      p.Total + s.Expense,
                    REPLACE(p.Hits, '#' + CAST(s.RowID AS VARCHAR(MAX)) + '#', '#') AS Hits,
                    p.TrackPath + '<ID>' + CAST(s.RowID AS VARCHAR(MAX)) + '</ID>' AS TrackPath
        FROM        @Sample AS s
        INNER JOIN  ctePack AS p ON p.Hits LIKE '%#' + CAST(s.RowID AS VARCHAR(MAX)) + '#%'
        WHERE       p.Total + s.Expense <= @WantedSum
)
INSERT      @Temp
            (
                TrackPath
            )
SELECT      MIN(TrackPath)
FROM        ctePack
WHERE       Total = @WantedSum
GROUP BY    Hits

When the iterations are over, and we have the wanted combniation(s), the task left is to report the records giving us the correct sum.
We also need the records grouped so that we can see which group each expense belong to. In same cases, one and the same record may used in multiple groups.
 
-- Display the final resultset
SELECT      t.CombID,
            s.RowID,
            s.Expense
FROM        @Temp AS t
CROSS APPLY t.TrackPath.nodes('/ID') AS f(n)
INNER JOIN  @Sample AS s ON s.RowID = f.n.value('.', 'INT')
ORDER BY    t.CombID,
            s.RowID


If you don't want to use XML, you can write the recursive cte like this (and drop the @temp table), to get all included records directly.


-- Calculate all possible permutations using recursion
;WITH ctePack(RowID, Expense, Total, Tracker)
AS (
        SELECT  s.RowID,
                s.Expense,
                s.Expense AS Total,
                (
                    SELECT      '#' + CAST(x.RowID AS VARCHAR(MAX))
                    FROM        @Sample AS x
                    WHERE       x.RowID <> s.RowID
                    ORDER BY    x.RowID
                    FOR XML     PATH('')
                ) + '#' AS Tracker
        FROM    @Sample AS s
        WHERE   s.Expense <= @WantedSum

        UNION ALL

        SELECT      s.RowID,
                    s.Expense,
                    p.Total + s.Expense,
                    REPLACE(p.Tracker, '#' + CAST(s.RowID AS VARCHAR(MAX)) + '#', '#') AS Tracker
        FROM        @Sample AS s
        INNER JOIN  ctePack AS p ON p.Tracker LIKE '%#' + CAST(s.RowID AS VARCHAR(MAX)) + '#%'
        WHERE       p.Total + s.Expense <= @WantedSum
)
SELECT  DISTINCT
        DENSE_RANK() OVER (ORDER BY Tracker) AS CombID,
        RowID,       
        Expense
FROM    ctePack
WHERE   Total = @WantedSum
Published Wednesday, June 30, 2010 2:42 PM by Peso

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

Internet Marketing said:

Peter Larsson : Another bin-packaging algorithm using recursion and XML

November 1, 2014 12:32 AM

Leave a Comment

(required) 
(required) 
Submit
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement