none
The Old Knapsack Algorithm - Would like to see quantities RRS feed

  • Question

  • The KnapSack class returns only the value of the items in the sack. I'm trying to find a way to have it also return the quantity of the items, for example how many of item 1, item 2, etc... Obviously there will be times it doesn't use all the items but once the capacity has been reached I want to solve how many of each item it selected. I tried using a new int[] called Qty[] but when the results come back it's not what I'm expecting and the number of items in the sack is clearly over the capacity. Any assistance would be appreciated and note this code does not work in it's current form.

    using System;
    namespace KnapsackAlgo
    {
        class KnapsackAlgorithm
        {
            static void Main(string[] args)
            {
                int[] cost = { 5, 3, 4 };
                int[] weight = { 1, 2, 4 };
                int[] Qty = { 0, 0, 0 };
                int capacity = 5;
                int itemsCount = cost.Length;
    
                int result = Knapsack.KnapSack(capacity, weight, cost, itemsCount);
                Console.WriteLine("{0,8:C}", result);
                Console.WriteLine("Qty of item #1 {0}", Qty[1]);
                Console.WriteLine("Qty of item #2 {0}", Qty[2]);
                Console.WriteLine("Qty of item #3 {0}", Qty[3]);
            }
        }
        public class Knapsack
        {
            public static int KnapSack(int capacity, int[] weight, int[] cost, int itemsCount)
            {
                int[,] K = new int[itemsCount + 1, capacity + 1];
    
                for (int i = 0; i <= itemsCount; ++i)
                {
                    for (int w = 0; w <= capacity; ++w)
                    {
                        if (i == 0 || w == 0)
                            K[i, w] = 0;
                        else if (weight[i - 1] <= w)
                            K[i, w] = Math.Max(cost[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]);
                        else
                            K[i, w] = K[i - 1, w];
                    }
                }
                return K[itemsCount, capacity];
            }
        }
    }
    Tuesday, August 6, 2019 2:40 PM

Answers

  • Allow me to compliment you on including a complete, runnable example with your question.  That makes it easier for us.  Well, it was ALMOST runnable; remember that the three items in your Qty array are numbered [0], [1], and [2].  Your reference to Qty[3] caused an exception.

    You don't ever pass the Qty array into the function, so obviously it is not being updated.  And the number of items is not over the capacity; as you have it now, you are placing one of item #0 and one of item #2, which results in a weight of 5 (which fits the capacity) and a cost of $9, which is optimal, given your conditions.  However, the code you have here (did it come from Wikipedia?) is solving the 0/1 knapsack problem.  It will never place more than 1 of any item.  Given that condition, your code is quite correct.

    In order to add multiple quantities, your code must get more complicated.  There is no clever solution to the knapsack problem.  You have to try every combination.  In your example, you could have from 0 to 5 of item #0, from 0 to 2 of item #1, and from 0 to 1 of item #2.

    You CAN solve this by using a different approach.  Start off with your Qty array at {0,0,0} like you have.  Now, if that arrangement fits the weight, compute the total cost of the arrangement.  If that's the new max, remember the quantities.  Then, bump to the next quantity.  That's the only tricky part.  You want to bump item #0 until it by itself exceeds the weight limit, then reset it to 0 and bump item #1.  When item #1 by itself exceeds the weight limit, set it to 0 and bump item #2.  When item #2 exceeds the weight limit, you've looked at all the possibilities.

    Just for your information, the optimal arrangement given your parameters is 5 of #0 and none of the rest.  That's a natural conclusion when the lightest item has the highest cost..


    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by Bill Tillman Wednesday, August 7, 2019 12:56 PM
    Tuesday, August 6, 2019 7:30 PM
  • And, by the way, computing the total weight of an arrangement and the total cost of an arrangement are the same operation: a dot product.  You should probably write a quick dot product function to make that part easier.

    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by Bill Tillman Wednesday, August 7, 2019 12:56 PM
    Tuesday, August 6, 2019 7:32 PM
  • Like this:

    using System;
    class KnapsackAlgorithm
    {
        static int dotprod( int[] q, int[] r )
        {
            int sum = 0;
            for( int i=0; i < q.Length; i++ )
                sum += q[i] * r[i];
            return sum;
        }
    
        static void Main(string[] args)
        {
            int[] cost = { 5, 3, 4 };
            int[] weight = { 1, 2, 4 };
            int capacity = 5;
    
            int[] Qty = { 0, 0, 0 };
            int maxcost = 0;
            int[] maxqty = { 0, 0, 0 };
    
            bool ok = true;
            while( ok )
            {
                // If this arrangement fits, see if it is a better cost.
    
                if( dotprod( Qty, weight ) <= capacity )
                {
                    int totcost = dotprod( Qty, cost );
                    if( totcost > maxcost )
                    {
                        maxcost = totcost;
                        Array.Copy( Qty, maxqty, Qty.Length );
                    }
                }
                
                // Advance to the next quantity.
    
                ok = false;
                for( int i=0; i < Qty.Length; i++ )
                {
                    if( (Qty[i]+1) * weight[i] <= capacity )
                    {
                        ok = true;
                        Qty[i] ++;
                        break;
                    }
                    Qty[i] = 0;
                }
            }
    
            Console.WriteLine( "{0} {1} {2} = {3}",
                maxqty[0], maxqty[1], maxqty[2], maxcost
            );
        }
    }
    


    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by Bill Tillman Wednesday, August 7, 2019 12:56 PM
    Tuesday, August 6, 2019 7:41 PM

All replies

  • Allow me to compliment you on including a complete, runnable example with your question.  That makes it easier for us.  Well, it was ALMOST runnable; remember that the three items in your Qty array are numbered [0], [1], and [2].  Your reference to Qty[3] caused an exception.

    You don't ever pass the Qty array into the function, so obviously it is not being updated.  And the number of items is not over the capacity; as you have it now, you are placing one of item #0 and one of item #2, which results in a weight of 5 (which fits the capacity) and a cost of $9, which is optimal, given your conditions.  However, the code you have here (did it come from Wikipedia?) is solving the 0/1 knapsack problem.  It will never place more than 1 of any item.  Given that condition, your code is quite correct.

    In order to add multiple quantities, your code must get more complicated.  There is no clever solution to the knapsack problem.  You have to try every combination.  In your example, you could have from 0 to 5 of item #0, from 0 to 2 of item #1, and from 0 to 1 of item #2.

    You CAN solve this by using a different approach.  Start off with your Qty array at {0,0,0} like you have.  Now, if that arrangement fits the weight, compute the total cost of the arrangement.  If that's the new max, remember the quantities.  Then, bump to the next quantity.  That's the only tricky part.  You want to bump item #0 until it by itself exceeds the weight limit, then reset it to 0 and bump item #1.  When item #1 by itself exceeds the weight limit, set it to 0 and bump item #2.  When item #2 exceeds the weight limit, you've looked at all the possibilities.

    Just for your information, the optimal arrangement given your parameters is 5 of #0 and none of the rest.  That's a natural conclusion when the lightest item has the highest cost..


    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by Bill Tillman Wednesday, August 7, 2019 12:56 PM
    Tuesday, August 6, 2019 7:30 PM
  • And, by the way, computing the total weight of an arrangement and the total cost of an arrangement are the same operation: a dot product.  You should probably write a quick dot product function to make that part easier.

    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by Bill Tillman Wednesday, August 7, 2019 12:56 PM
    Tuesday, August 6, 2019 7:32 PM
  • Like this:

    using System;
    class KnapsackAlgorithm
    {
        static int dotprod( int[] q, int[] r )
        {
            int sum = 0;
            for( int i=0; i < q.Length; i++ )
                sum += q[i] * r[i];
            return sum;
        }
    
        static void Main(string[] args)
        {
            int[] cost = { 5, 3, 4 };
            int[] weight = { 1, 2, 4 };
            int capacity = 5;
    
            int[] Qty = { 0, 0, 0 };
            int maxcost = 0;
            int[] maxqty = { 0, 0, 0 };
    
            bool ok = true;
            while( ok )
            {
                // If this arrangement fits, see if it is a better cost.
    
                if( dotprod( Qty, weight ) <= capacity )
                {
                    int totcost = dotprod( Qty, cost );
                    if( totcost > maxcost )
                    {
                        maxcost = totcost;
                        Array.Copy( Qty, maxqty, Qty.Length );
                    }
                }
                
                // Advance to the next quantity.
    
                ok = false;
                for( int i=0; i < Qty.Length; i++ )
                {
                    if( (Qty[i]+1) * weight[i] <= capacity )
                    {
                        ok = true;
                        Qty[i] ++;
                        break;
                    }
                    Qty[i] = 0;
                }
            }
    
            Console.WriteLine( "{0} {1} {2} = {3}",
                maxqty[0], maxqty[1], maxqty[2], maxcost
            );
        }
    }
    


    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by Bill Tillman Wednesday, August 7, 2019 12:56 PM
    Tuesday, August 6, 2019 7:41 PM
  • Many thanks to you Tim. I'm just getting back into C# after about 3 years of inactivity with another job so my familiarity with coding is a bit rusty. Make that very rusty.

    Yes, this KnapSack code was first introduced to me in 2015 by one of the most arrogant, close minded managers I've ever worked with. He basically threw it at the team and said here this will work. At that time our task was to figure out the lowest costs for an unknown combination of some compression springs. The total number of different springs, each with a different force was 7. And somehow I made it work although it never really functioned like I fully wanted it to.  Now the trick was our suppliers were constantly changing the design of the springs and thus the forces changed as well as the number of types was sometimes reduced to say 4 or 5 or at one point it was increased to 10 so designing the code to be flexible was important. BTW, the manager who proposed the KnapSack algorithm never got it working properly either. A short time later the company was sold and the project was abandoned. I searched through all my backups but was never able to find the code I did some three years ago so I'm starting again from scratch.

    In my example, the weight is actually the force of the spring so I'm looking for the max force with the lowest cost and not exceed the capacity. It's obvious I have some more work to do on this, but I'm always up to a challenge.

    Thanks again, I'll keep trying and will post results if and when I get it.

    Wednesday, August 7, 2019 12:56 PM