0/1 Knapsack - A few clarification on Wiki's pseudocode

Question

Here's the code on en.wikipedia's article on the Knapsack problem:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
  m[0, w] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

I've got two points which my tired brain cannot work out. They're minor, I'm sure, but I could really use the help.

•What's the size of the m[] array? m[n,W]? If it is, is the pseudocode ignoring the last line and last column, because it fills the entire first line with zeroes (the for() loop with m[0,w] := 0), and then loops from 1 to n, and 0 to W. For example, for 3 different items (n==3) and a capacity of 4 (W==3), is m[3,4] or m[4,5]?

•Are there better examples of a dynamic knapsack algo, somewhere?

Answer 1

The size of the array is (n + 1) × (W + 1), since the values range up from [0, 0] through [n, W] inclusive.

The interpretation of the grid is the following: position [k, w] represents the maximum amount of value that you can get from using the first k items (assuming the items are numbered 1, 2, ..., n) and carrying no more than w total weight.

The reason that the first row is set entirely to 0 is because any entry of the form [0, w] corresponds to the maximum value you can get using the first 0 items and carrying at most w weight. This is always zero, since you can never get any value by not picking any items. This corresponds to the base case of the recursion.

Rows after the first are filled in using the following idea: if you want to try picking the kth item, you would first need to make sure that you have the ability to hold it (meaning that w has to be at least w[k]). If you can't hold it, your best option is to make the most of the first k - 1 items subject to your current weight restriction (so you'd be best off taking the value corresponding to m[k - 1, w]. If you can hold the item, your options are either to not take it (and, as before, to make the most of the other items, yielding m[k - 1, w]), or to take it and maximize the remaining carrying capacity with the remaining items. This gives you value v[k] + m[k - 1, w - w[k]].

Hope this helps!

Answer 2

I know its been already answered, just adding code versions in c#, just for reference (for simplified knapsack you may refer to: How do I solve the 'classic' knapsack algorithm recursively?):

version 1. Solving using Dynamic Programming (similar to wiki) - Bottom Up (tabulated approach)

version 2. Solving using Dynamic Programming but Top to bottom (Memoization - lazy)

version 3. Recursive (just recursive solution without using overlapped sub problems or optimal substructure properties that enable to use DP)

version 4. Brute force (going through all combinations)

References: http://en.wikipedia.org/wiki/Knapsack_problem, How do I solve the 'classic' knapsack algorithm recursively?

Tabular - DP - Version (O(nW) - pseudo polynomial) - O(nW) memory - Bottom up

public int Knapsack_0_1_DP_Tabular_Bottom_Up(int[] weights, int[] values, int maxWeight)
        {
            this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
            int[][] DP_Memoization_Max_Value_Cache = new int[values.Length + 1][];
            for (int i = 0; i <= values.Length; i++)
            {
                DP_Memoization_Max_Value_Cache[i] = new int[maxWeight + 1];
                for (int j = 0; j <= maxWeight; j++)
                {
                    DP_Memoization_Max_Value_Cache[i][j] = 0; //yes, its default - 
                }
            }
            /// f(i, w) = f(i-1, w) if Wi > w
            ///         Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
            ///         Or 0 if i < 0 
            for(int i = 1; i<=values.Length; i++)
            {
                for(int w = 1; w <= maxWeight; w++)
                {
                    //below code can be refined - intentional as i just want it
                    //look similar to other 2 versions (top_to_bottom_momoization
                    //and recursive_without_resuing_subproblem_solution
                    int maxValueWithoutIncludingCurrentItem =
                            DP_Memoization_Max_Value_Cache[i - 1][w];
                    if (weights[i - 1] > w)
                    {
                        DP_Memoization_Max_Value_Cache[i][w] = maxValueWithoutIncludingCurrentItem;
                    }
                    else
                    {
                        int maxValueByIncludingCurrentItem =
                            DP_Memoization_Max_Value_Cache[i - 1][w - weights[i - 1]]
                            + values[i-1];
                        int overAllMax = maxValueWithoutIncludingCurrentItem;
                        if(maxValueByIncludingCurrentItem > overAllMax)
                        {
                            overAllMax = maxValueByIncludingCurrentItem;   
                        }
                        DP_Memoization_Max_Value_Cache[i][w] = overAllMax;
                    }
                }
            }
            return DP_Memoization_Max_Value_Cache[values.Length][maxWeight];
        }

DP - Memoization - Top to Bottom - Lazy evaluation

/// <summary>
        /// f(i, w) = f(i-1, w) if Wi > w
        ///         Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
        ///         Or 0 if i < 0 
        /// </summary>
        int Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive(int[] weights, int[] values,
            int index, int weight, int?[][] DP_Memoization_Max_Value_Cache)
        {
            if (index < 0)
            {
                return 0;
            }
            Debug.Assert(weight >= 0);
#if DEBUG
            if ((index == 0) || (weight == 0))
            {
                Debug.Assert(DP_Memoization_Max_Value_Cache[index][weight] == 0);
            }
#endif
            //value is cached, so return
            if(DP_Memoization_Max_Value_Cache[index][weight] != null)
            {
                return DP_Memoization_Max_Value_Cache[index][weight].Value;
            }
            Debug.Assert(index > 0);
            Debug.Assert(weight > 0);
            int maxValueWithoutIncludingCurrentItem = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive
                (weights, values, index - 1, weight, DP_Memoization_Max_Value_Cache);
            if (weights[index-1] > weight)
            {
                DP_Memoization_Max_Value_Cache[index][weight] = maxValueWithoutIncludingCurrentItem;
                //current item weight is more, so we cant include - so, just return
                return maxValueWithoutIncludingCurrentItem;
            }
            int overallMaxValue = maxValueWithoutIncludingCurrentItem;
            int maxValueIncludingCurrentItem = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive
                (weights, values, index - 1, weight - weights[index-1],
                    DP_Memoization_Max_Value_Cache) + values[index - 1];
            if(maxValueIncludingCurrentItem > overallMaxValue)
            {
                overallMaxValue = maxValueIncludingCurrentItem;
            }
            DP_Memoization_Max_Value_Cache[index][weight] = overallMaxValue;
            return overallMaxValue;
        }

And public method to call (for details on callers, refer to below units tests)

public int Knapsack_0_1_DP_Tabular_Bottom_Up(int[] weights, int[] values, int maxWeight)
        {
            this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
            int[][] DP_Memoization_Max_Value_Cache = new int[values.Length + 1][];
            for (int i = 0; i <= values.Length; i++)
            {
                DP_Memoization_Max_Value_Cache[i] = new int[maxWeight + 1];
                for (int j = 0; j <= maxWeight; j++)
                {
                    DP_Memoization_Max_Value_Cache[i][j] = 0; //yes, its default - 
                }
            }
            /// f(i, w) = f(i-1, w) if Wi > w
            ///         Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
            ///         Or 0 if i < 0 
            for(int i = 1; i<=values.Length; i++)
            {
                for(int w = 1; w <= maxWeight; w++)
                {
                    //below code can be refined - intentional as i just want it
                    //look similar to other 2 versions (top_to_bottom_momoization
                    //and recursive_without_resuing_subproblem_solution
                    int maxValueWithoutIncludingCurrentItem =
                            DP_Memoization_Max_Value_Cache[i - 1][w];
                    if (weights[i - 1] > w)
                    {
                        DP_Memoization_Max_Value_Cache[i][w] = maxValueWithoutIncludingCurrentItem;
                    }
                    else
                    {
                        int maxValueByIncludingCurrentItem =
                            DP_Memoization_Max_Value_Cache[i - 1][w - weights[i - 1]]
                            + values[i-1];
                        int overAllMax = maxValueWithoutIncludingCurrentItem;
                        if(maxValueByIncludingCurrentItem > overAllMax)
                        {
                            overAllMax = maxValueByIncludingCurrentItem;   
                        }
                        DP_Memoization_Max_Value_Cache[i][w] = overAllMax;
                    }
                }
            }
            return DP_Memoization_Max_Value_Cache[values.Length][maxWeight];
        }

Recursive - with DP sub problems - but without reusing overlapping sub problems (this should depict how it is easier to change recursive version to DP Top to bottom (Memoization version)

public int Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(int[] weights, int[] values, int maxWeight)
        {
            this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
            int v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights, values, index: weights.Length-1, weight: maxWeight);
            return v;
        }
        /// <summary>
        /// f(i, w) = f(i-1, w) if Wi > w
        ///         Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
        ///         Or 0 if i < 0 
        /// </summary>
        int Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(int[] weights, int[] values, int index, int weight)
        {
            if (index < 0)
            {
                return 0;
            }
            Debug.Assert(weight >= 0);
            int maxValueWithoutIncludingCurrentItem = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights,
                values, index - 1, weight);
            if(weights[index] > weight)
            {
                //current item weight is more, so we cant include - so, just return
                return maxValueWithoutIncludingCurrentItem;
            }
            int overallMaxValue = maxValueWithoutIncludingCurrentItem;
            int maxValueIncludingCurrentItem = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights,
                values, index - 1, weight - weights[index]) + values[index];
            if(maxValueIncludingCurrentItem > overallMaxValue)
            {
                overallMaxValue = maxValueIncludingCurrentItem;
            }
            return overallMaxValue;
        }

Brute Force (going through all combinations)

private int _maxValue = int.MinValue;
        private int[] _valueIndices = null;
        public void Knapsack_0_1_BruteForce_2_Power_N(int[] weights, int[] values, int maxWeight)
        {
            this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
            this._maxValue = int.MinValue;
            this._valueIndices = null;
            this.Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, 0, 0, 0, new List<int>());
        }
        private void Knapsack_0_1_BruteForce_2_Power_N_Rcursive(int[] weights, int[] values, int maxWeight, int index, int currentWeight, int currentValue, List<int> currentValueIndices)
        {
            if(currentWeight > maxWeight)
            {
                return;
            }
            if(currentValue > this._maxValue)
            {
                this._maxValue = currentValue;
                this._valueIndices = currentValueIndices.ToArray();
            }
            if(index == weights.Length)
            {
                return;
            }
            Debug.Assert(index < weights.Length);
            var w = weights[index];
            var v = values[index];
            //see if the current value, conributes to max value
            currentValueIndices.Add(index);
            Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, index + 1, currentWeight + w,
                currentValue + v, currentValueIndices);
            currentValueIndices.Remove(index);
            //see if current value, does not contribute to max value
            Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, index + 1, currentWeight, currentValue,
                currentValueIndices);
        }

Unit Tests 1

[TestMethod]
        public void Knapsack_0_1_Tests()
        {
            int[] benefits = new int[] { 60, 100, 120 };
            int[] weights = new int[] { 10, 20, 30 };
            this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 50);
            Assert.IsTrue(this._maxValue == 220);
            int v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights, 
                values: benefits, maxWeight: 50);
            Assert.IsTrue(v == 220);
            v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
                values: benefits, maxWeight: 50);
            Assert.IsTrue(v == 220);
            v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
                values: benefits, maxWeight: 50);
            Assert.IsTrue(v == 220);
            benefits = new int[] { 3, 4, 5, 8, 10 };
            weights = new int[] { 2, 3, 4, 5, 9 };
            this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 20);
            Assert.IsTrue(this._maxValue == 26);
            v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights, values: benefits,
                maxWeight: 20);
            Assert.IsTrue(v == 26);
            v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
                values: benefits, maxWeight: 20);
            Assert.IsTrue(v == 26);
            v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
                values: benefits, maxWeight: 20);
            Assert.IsTrue(v == 26);
            benefits = new int[] { 3, 4, 5, 6};
            weights = new int[] { 2, 3, 4, 5 };
            this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 5);
            Assert.IsTrue(this._maxValue == 7);
            v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights, values: benefits,
                maxWeight: 5);
            Assert.IsTrue(v == 7);
            v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
                values: benefits, maxWeight: 5);
            Assert.IsTrue(v == 7);
            v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
                values: benefits, maxWeight: 5);
            Assert.IsTrue(v == 7);
        }

Unit Tests 2

[TestMethod]
        public void Knapsack_0_1_Brute_Force_Tests()
        {
            int[] benefits = new int[] { 60, 100, 120 };
            int[] weights = new int[] { 10, 20, 30 };
            this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 50);
            Assert.IsTrue(this._maxValue == 220);
            Assert.IsTrue(this._valueIndices.Contains(1));
            Assert.IsTrue(this._valueIndices.Contains(2));
            Assert.IsTrue(this._valueIndices.Length == 2);
            this._maxValue = int.MinValue;
            this._valueIndices = null;
            benefits = new int[] { 3, 4, 5, 8, 10 };
            weights = new int[] { 2, 3, 4, 5, 9 };
            this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 20);
            Assert.IsTrue(this._maxValue == 26);
            Assert.IsTrue(this._valueIndices.Contains(0));
            Assert.IsTrue(this._valueIndices.Contains(2));
            Assert.IsTrue(this._valueIndices.Contains(3));
            Assert.IsTrue(this._valueIndices.Contains(4));
            Assert.IsTrue(this._valueIndices.Length == 4);
        }