Modified Knapsack/Subset-Sum with same weight/values

Question

I was working on a problem that has to deal with a special case of the Knapsack/Subset-Sum Problem. The problem is as follows:

You have a set of bundle sizes in decreasing sizes that are random like: {47, 35, 22, ...}. You have value that is the quantity of widgets like: #widgets = 33. Find the least number of bundles that can make up the number of widgets for the bundle. If there is no way to return set that equals quantities then return null.

• Example 1:
  • Bundle Sizes: 46, 25, 12, 4, 3
  • quantity: 30
  • Returned Value: {46:0, 25:0, 12:2, 4:0, 3:2} (bundle size:# of bundles)
• Example 2:
  • Bundle Sizes: 46, 25, 12, 4, 3
  • quantity: 17
  • Returned Value: {46:0, 25:0, 12:0, 4:2, 3:3}
• Example 3:
  • Bundle Sizes: 46, 25, 12, 4, 3
  • quantity: 47
  • Returned Value: {46:0, 25:1, 12:1, 4:1, 3:2}
• Example 4:
  • Bundle Sizes: 46, 25, 12, 4, 3
  • quantity: 5
  • Returned Value: null

How would go about this problem?

I have written a program in C# that does close enough job but resets an index in a for loop to dump bundle sizes that will not work with the rest of the set. Will post source if requested for how far it goes.

Requested code:

public List<int> BreakDown(List<int> bunSize, int buySize)
    {
        List<int> tempBunSize = bunSize.ToList();
        tempBunSize.RemoveAll(e => e > buySize);

        List<int> ammountNeeded = new List<int>();
        int result = buySize;

        for (int index = 0; index < tempBunSize.Count; index++)
        {       
            int size = tempBunSize[index];
            int tempResult = 0;
            double calcResult = 0;
            int addAmmount = 0;

            if (index == tempBunSize.Count - 2)
            {
                tempResult = result % size;

                if ((tempBunSize.Count > 2 || result % tempBunSize[tempBunSize.Count - 1] == 0))
                {
                    if (result % size != 0)
                    {
                        ammountNeeded.Add(0);
                        tempResult = result % tempBunSize[tempBunSize.Count - 1];

                        if (tempResult != 0)
                        {
                            tempResult = result;
                            int sizeInc = 0;
                            while (tempResult != 0)
                            {
                                tempResult = tempResult - size;
                                sizeInc++;
                                if (tempResult < 0)
                                {
                                    int decreaseOne = ammountNeeded.First();
                                    ammountNeeded[0] = --decreaseOne;
                                    result = result + tempBunSize.First();
                                    if (ammountNeeded[0] <= 0)
                                    {
                                        tempBunSize.RemoveAt(0);
                                        index = 0;
                                        ammountNeeded = new List<int>();
                                    }
                                    ammountNeeded.Remove(0);
                                    --index;
                                    break;
                                }
                                if (tempResult % tempBunSize[tempBunSize.Count - 1] == 0)
                                {
                                    ammountNeeded.Remove(0);
                                    ammountNeeded.Add(sizeInc);
                                    ammountNeeded.Add(tempResult / tempBunSize[tempBunSize.Count - 1]);
                                    break;
                                }
                            }
                            if (tempResult < 0) continue;
                            break;
                        }
                        else
                        {
                            calcResult = result / tempBunSize[tempBunSize.Count - 1];
                            addAmmount = (int)Math.Floor(calcResult);
                            ammountNeeded.Add(addAmmount);
                            break;
                        }
                    }
                    else if (result % size == 0)
                    {
                        tempResult = result % size;
                        if (tempResult != 0 && result % tempBunSize[tempBunSize.Count - 1] != 0)
                        {
                            int decreaseOne = ammountNeeded.First();
                            ammountNeeded.Insert(0, --decreaseOne);
                            result = result + tempBunSize.First();
                            continue;
                        }
                        else
                        {
                            calcResult = result / size;
                            addAmmount = (int)Math.Floor(calcResult);
                            ammountNeeded.Add(addAmmount);

                            if (result % size == 0)
                            {
                                ammountNeeded.Add(0);
                                break;
                            }
                            calcResult = result / tempBunSize[tempBunSize.Count - 1];
                            addAmmount = (int)Math.Floor(calcResult);
                            ammountNeeded.Add(addAmmount);
                            break;
                        }
                    }
                }
                else if (tempResult % tempBunSize[tempBunSize.Count - 1] != 0)
                {
                    tempResult = result;
                    int sizeInc = 0;
                    while (tempResult != 0)
                    {
                        tempResult = tempResult - size;
                        sizeInc++;
                        if (tempResult % tempBunSize[tempBunSize.Count - 1] == 0)
                        {
                            ammountNeeded.Add(sizeInc);
                            ammountNeeded.Add(tempResult / tempBunSize[tempBunSize.Count - 1]);
                            break;
                        }

                    }
                    break;
                }
                else if (result == 0)
                {
                    while (ammountNeeded.Count < bunSize.Count)
                    {
                        ammountNeeded.Add(0);
                    }
                    break;
                }
                else
                {
                    calcResult = result / size;
                    ammountNeeded.Add((int)Math.Floor(calcResult));

                    calcResult = tempResult / tempBunSize[tempBunSize.Count - 1];
                    ammountNeeded.Add((int)Math.Floor(calcResult));
                    break;
                }
            }
            ammountNeeded.Add((int)Math.Floor((decimal)result / size));
            result = result % size;
            if (result == 0) continue;

        }

        if (ammountNeeded.Count < bunSize.Count)
        {
            ammountNeeded.Reverse(0, ammountNeeded.Count);
            while (ammountNeeded.Count < bunSize.Count)
            {
                ammountNeeded.Add(0);
            }
            ammountNeeded.Reverse(0, ammountNeeded.Count);
        }
        if (ammountNeeded.FindLast(e => e < 0) < 0 || ammountNeeded.Sum() == 0)
            return null;
        return ammountNeeded;
    }
}

Answer 1

This was a FUN problem to solve. Geek points all around.

Your main problem I believe is in trying to loop through a single list. Really what you want here is to test all variations of the list then find the one with the highest values.

Also, as is stated in the comments, recursion is your friend here. I recursed through each permutation of the bundle amounts.

One problem that your data has is that of your 17 example. The math used in this example is greedy. Meaning, 4 is going to try to get as many as it can before it hands off the remainder to 3. 4 therefore gets 4 bundles and with 1 remainder a null is returned. For this reason I think the correct answer to 17 should be null. You might be able to figure out how to balance between numbers, but that'll be a whole lot more logic IMO.

Here is the code:

public class test
{
    public static void Main()
    {
        var bundleSizes = new List<int> { 46, 25, 12, 4, 3 };

        var quantity = 30;
        var bundleResults = Begin(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        quantity = 17;
        bundleResults = Begin(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        quantity = 47;
        bundleResults = Begin(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        quantity = 5;
        bundleResults = Begin(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        Console.Read();
    }

    static void Output(List<int> bundleSizes, int quantity, Dictionary<int, int> bundleResults)
    {
        var fullResults = new Dictionary<int, int>();
        bundleSizes.ForEach(
            delegate(int e)
                {
                    var result = 0;
                    if(bundleResults != null)
                        bundleResults.TryGetValue(e, out result);
                    fullResults.Add(e, result);
                });
        Console.WriteLine("Bundle Sizes: {0}", string.Join(",", bundleSizes));
        Console.WriteLine("Quantity: {0}", quantity);
        Console.WriteLine("Returned Value: {0}", bundleResults == null ? "null" : fullResults.Aggregate("", (keyString, pair) => keyString + pair.Key + ":" + pair.Value + ","));
    }

    static Dictionary<int, int> Begin(List<int> bundleSizes, int quantity)
    {
        var bundleCombinations = GetCombination(bundleSizes);
        var tempBundleSizes = new List<Dictionary<int, int>>();
        foreach (var bundleCombination in bundleCombinations)
        {
            var tempBundleSize = new Dictionary<int, int>();
            bundleCombination.ForEach(e => tempBundleSize.Add(e, 0));
            var results = Bundle(bundleCombination, quantity);
            if (results == null)
                continue;
            foreach (var result in results)
            {
                tempBundleSize[result.Key] = result.Value;
            }
            tempBundleSizes.Add(tempBundleSize);
        }
        var longest = tempBundleSizes.OrderByDescending(x => x.Count).FirstOrDefault();
        return longest;
    }

    static List<List<int>> GetCombination(List<int> list)
    {
        var retValue = new List<List<int>>();
        var count = Math.Pow(2, list.Count);
        for (var i = 1; i <= count - 1; i++)
        {
            var retList = new List<int>();
            var str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
            for (var j = 0; j < str.Length; j++)
            {
                if (str[j] == '1')
                {
                    retList.Add(list[j]);
                }
            }
            retValue.Add(retList);
        }
        return retValue;
    }

    static Dictionary<int, int> Bundle(List<int> bundleSizes, int quantity)
    {
        var bundleQuantities = new Dictionary<int, int>();
        bundleSizes.ForEach(delegate(int k)
        {
            if (k <= quantity)
                bundleQuantities.Add(k, 0);
        });
        return bundleQuantities.Count == 0 ? null : RecurseBundles(quantity, bundleQuantities.Keys.ToList(), bundleQuantities);
    }

    static Dictionary<int, int> RecurseBundles(int quantity, List<int> bundleSizes, Dictionary<int, int> bundleQuantities)
    {
        var bundleSize = bundleSizes.First();
        var bundles = (int)Math.Floor((double)quantity / bundleSize);
        var remainingQuantity = quantity % bundleSize;
        bundleQuantities[bundleSize] = bundles;
        var remainingBundles = bundleSizes.Skip(1).ToList();
        if (!remainingBundles.Any() && remainingQuantity > 0)
            bundleQuantities = null;
        if (remainingBundles.Any())
            bundleQuantities = RecurseBundles(remainingQuantity, remainingBundles, bundleQuantities);
        return bundleQuantities;
    }
}

Here is the output:

Bundle Sizes: 46,25,12,4,3
Quantity: 30
Returned Value: 46:0,25:0,12:2,4:0,3:2,
Bundle Sizes: 46,25,12,4,3
Quantity: 17
Returned Value: null
Bundle Sizes: 46,25,12,4,3
Quantity: 47
Returned Value: 46:0,25:0,12:3,4:2,3:1,
Bundle Sizes: 46,25,12,4,3
Quantity: 5
Returned Value: null

Special thanks to these fantastic SO answers:

All Possible Combinations of a list of Values

How do I combine the keys and values of a Dictionary into one List using LINQ?

Find max count of a list of custom types

EDIT: Made a small change for a better formatted output in the Output method

Answer 2

Worked more on the solution and thanks to a co-worker and paqogomez's answer we got the correct code that works for all my examples and more! My co-worker showed me that you can use a stack in place of recursion and use the stack to keep track of the index that looks to the left and right of the bundle list. This code uses a Greedy Brute-force solution, if there is a faster way I will be interested!

C# Code:

class Program
{
    public static void Main()
    {
        List<int> bundleSizes = new List<int> { 46, 25, 12, 4, 3 };
        int quantity = 30;
        Dictionary<int, int> bundleResults = StackThis(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        quantity = 17;
        bundleResults = StackThis(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        quantity = 47;
        bundleResults = StackThis(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        quantity = 5;
        bundleResults = StackThis(bundleSizes, quantity);
        Output(bundleSizes, quantity, bundleResults);

        Console.Read();
    }

    // Reused paqogomez output
    static void Output(List<int> bundleSizes, int quantity, Dictionary<int, int> bundleResults)
    {
        var fullResults = new Dictionary<int, int>();
        bundleSizes.ForEach(
            delegate(int e)
            {
                var result = 0;
                if (bundleResults != null)
                    bundleResults.TryGetValue(e, out result);
                fullResults.Add(e, result);
            });
        Console.WriteLine("Bundle Sizes: {0}", string.Join(",", bundleSizes));
        Console.WriteLine("Quantity: {0}", quantity);
        Console.WriteLine("Returned Value: {0}", bundleResults == null ? "null" : fullResults.Aggregate("", (keyString, pair) => keyString + pair.Key + ":" + pair.Value + ","));
    }

    static private Dictionary<int, int> StackThis(List<int> usableBundle, int currentQuantity)
    {
        // Order the list from largest bundle size to smallest size
        List<int> arrUsableBundles = usableBundle.OrderByDescending(x => x).ToList();

        // Key: Bundles | Value: Quantity
        Dictionary<int, int> hmBundleToQuantity = new Dictionary<int, int>();

        // Create the hashmap table structure
        foreach (int Bundle in arrUsableBundles)
        {
            hmBundleToQuantity.Add(Bundle, 0);
        }

        // Keep track of our index of the bundles we need to figure out
        Stack<int> stBundleIndex = new Stack<int>();

        // Used to calculate the left and right of bundle list
        int ixCursor;

        // Our remaining quantity after calculations
        int iRemaining;

        /*
            This will act as the midpoint of the bundle list
            Will update the right of the cursor, decrement the
            cursor, don’t touch the left, and since the loop 
            hasn’t started we’ll consider everything updatable
            and on the right of the cursor
        */
        stBundleIndex.Push(-1);

        // Keep working till there is no more ways to solve the solution
        while (stBundleIndex.Count > 0)
        {
            // The current cursor is always removed and needs to
            // be added back if we want to check it again
            ixCursor = stBundleIndex.Pop();

            iRemaining = currentQuantity;

            for (int ixBundle = 0; ixBundle < usableBundle.Count; ++ixBundle)
            {
                //Left of current scope, values remain the same
                if (ixBundle < ixCursor)
                {
                    iRemaining -= (hmBundleToQuantity[usableBundle[ixBundle]] * usableBundle[ixBundle]);
                }

                //At the cursor stack scope – decrement current quantity
                if (ixBundle == ixCursor)
                {
                    --hmBundleToQuantity[usableBundle[ixBundle]];
                    iRemaining -= (hmBundleToQuantity[usableBundle[ixBundle]] * usableBundle[ixBundle]);
                }

                //Right of current scope gets calculated
                if (ixBundle > ixCursor)
                {
                    hmBundleToQuantity[usableBundle[ixBundle]] += iRemaining / usableBundle[ixBundle];
                    iRemaining = iRemaining % usableBundle[ixBundle];
                }
            }

            if (iRemaining == 0) return hmBundleToQuantity;

            // Otherwise… We have nothing left on the stack we’ll check
            // back to the beginning for non-zero values
            int iNonEmptyStart = 0;

            //Keep the current scope on the stack if the quantity is still bigger than zero
            if (ixCursor >= 0 && hmBundleToQuantity[usableBundle[ixCursor]] > 0)
            {
                stBundleIndex.Push(ixCursor);

                // Maximum cursor on the stack
                // (this way we don’t decrement further back than we want)
                iNonEmptyStart = stBundleIndex.Max();
            }

            //Add last non-empty value to the stack to decrement and recalculate from there
            for (int ixNonEmpty = usableBundle.Count - 1; ixNonEmpty >= iNonEmptyStart; ixNonEmpty--)
            {
                if (hmBundleToQuantity[usableBundle[ixNonEmpty]] > 0)
                {
                    stBundleIndex.Push(ixNonEmpty);
                    break;
                }
            }
        }
        return null;
    }
}

Once again thanks for all the help on this and special thanks to my co-worker and paqogomez on some help to the solution!