apply best fitted discount package on items automatically

I have created some discount packages:

Package1(Item1,Item2,Item5) Discount-5%.
Package2(Item2,Item5,Item8) Discount-8% 
Package3(Item1,Item2) Discount3%.

When a Person buy Items Online(for Ex. he bu开发者_如何学Cys Item1,Item2,Item5, Item10), while I show him the total price, I need to apply the best fitted discount on the items automatically.

In the above case, two discounts would be applicable on said selection, however Package1 Discount is best as it give a person max benefit... so this I need apply this automatically.

Is there anyone who came across this type of scenario or anyone who could help me?

DiscountID DiscountName ItemIds Disc%

1 Package1 1,2,5 5
2 Package2 2,3,5 8
3 Package3 1,2 3

I have all the ItemId with me, which a Person selected. Now need to apply best fit discount..

Appreciating your help/ guidance.

Try this

-- Test tables
CREATE TABLE #Package(Name varchar(50), Discount decimal(10,2))
CREATE TABLE #PackageItem(PackageName varchar(50), ProductName varchar(50))
CREATE TABLE #ShoppingCart(ProductName varchar(50))

-- Test data
INSERT INTO #Package VALUES ('Package1', 0.05)
INSERT INTO #PackageItem VALUES ('Package1', 'Item1')
INSERT INTO #PackageItem VALUES ('Package1', 'Item2')
INSERT INTO #PackageItem VALUES ('Package1', 'Item5')
INSERT INTO #Package VALUES ('Package2', 0.08)
INSERT INTO #PackageItem VALUES ('Package2', 'Item1')
INSERT INTO #PackageItem VALUES ('Package2', 'Item5')
INSERT INTO #PackageItem VALUES ('Package2', 'Item8')
INSERT INTO #Package VALUES ('Package3', 0.03)
INSERT INTO #PackageItem VALUES ('Package3', 'Item1')
INSERT INTO #PackageItem VALUES ('Package3', 'Item2')

INSERT INTO #ShoppingCart VALUES ('Item1')
INSERT INTO #ShoppingCart VALUES ('Item2')
INSERT INTO #ShoppingCart VALUES ('Item5')
INSERT INTO #ShoppingCart VALUES ('Item10')

SELECT  TOP 1 *
FROM    (
    -- Join #ShoppingCart with PackageItem and count matched rows
    SELECT      #Package.Name, #Package.Discount,
                COUNT(#Package.Name) AS [Count]
    FROM        #ShoppingCart
    LEFT JOIN   #PackageItem 
                ON #PackageItem.ProductName = #ShoppingCart.ProductName
    LEFT JOIN   #Package ON #Package.Name = #PackageItem.PackageName
    GROUP BY    #Package.Name, #Package.Discount
        ) A
JOIN
        (
    -- Count how many products each package have
    SELECT      #Package.Name,
                COUNT(#Package.Name) AS [Count]
    FROM        #Package
    LEFT JOIN   #PackageItem ON #Package.Name = #PackageItem.PackageName
    GROUP BY    #Package.Name, #Package.Discount
        ) B
-- if same package contains same number of products, pick it
-- (so you can't have a same item twice in your cart;
--  but you probably already have a quantity column)
ON A.Name = B.Name AND A.[Count] = B.[Count]
-- just greater discount matters
ORDER BY A.Discount DESC

-- Clear test stuff
DROP TABLE #Package
DROP TABLE #PackageItem
DROP TABLE #ShoppingCart

You need to apply each set of purchased items to each package, either returning the discount %, or zero, if they don't qualify, then query those results for the max discount from your set of packages.

At first glance, it seems like this is an instance of the Knapsack Problem, which is NP-hard.

This paper seems to address a similar problem to yours.

Brute Force Solution

One brute force solution would be to apply every valid combination of discount packages to the order.

Picture a tree where, for a given node, each ancestor represents a discount package that has already been applied to the order, and each of its children represent a valid discount package that can be applied to the remaining items in the order.

A node is a leaf when no more packages can be applied to the order.

I wouldn't recommend this if you have a large number of items and more than 1 discount package being offered.