Thursday, August 7, 2014

Knapsack (0/1, unbound) Problem

Excerpt from wiki (http://en.wikipedia.org/wiki/Knapsack_problem):

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Knapsack 0/1

Basically the constraint is an item can be selected at most only once.

say f[i, w] is the maximum value that can be obtained using up-to 'i' elements so that sum of their weights is at most 'w'

f[i, w] = 0 if i <= 0
              0 if w == 0
              f[i-1, w] if weights[i] > w
              max (f[i-1, w], f[i-1, w-weights[i]] + values[i])

Unbound Knapsack

basically there is no bound on the number of times an item can be selected
 
f[i, w] = 0 if i <= 0
              0 if w == 0
              f[i-1, w] if weights[i] > w
              max (f[i-1, w], f[i, w-weights[i]]+ vi)
 
 
 Below is the corresponding code -

Using Memoization


Code Snippet
  1. public int Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(int[] weights, int[] values, int maxWeight)
  2.         {
  3.             this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
  4.             int?[][] DP_Memoization_Max_Value_Cache = new int?[values.Length+1][];
  5.             for(int i = 0; i<=values.Length; i++)
  6.             {
  7.                 DP_Memoization_Max_Value_Cache[i] = new int?[maxWeight+1];
  8.                 for(int j = 0; j <= maxWeight; j++)
  9.                 {
  10.                     DP_Memoization_Max_Value_Cache[i][j] = null; //yes, its default - just to be defensive
  11.                     if(i == 0)
  12.                     {
  13.                         DP_Memoization_Max_Value_Cache[0][j] = 0;
  14.                     }
  15.                 }
  16.                 //value for weight zero is zero :)
  17.                 DP_Memoization_Max_Value_Cache[i][0] = 0;
  18.             }
  19.             var v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive(weights, values,
  20.                 index: values.Length, weight: maxWeight,
  21.                 DP_Memoization_Max_Value_Cache: DP_Memoization_Max_Value_Cache);
  22.             Assert.IsTrue(v == DP_Memoization_Max_Value_Cache[values.Length][maxWeight]);
  23.             return v;
  24.         }
  25.         /// <summary>
  26.         /// f(i, w) = f(i-1, w) if Wi > w
  27.                  ///Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
  28.                  ///Or 0 if i < 0
  29.         /// </summary>
  30.         int Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive(int[] weights, int[] values,
  31.             int index, int weight, int?[][] DP_Memoization_Max_Value_Cache)
  32.         {
  33.             if (index < 0)
  34.             {
  35.                 return 0;
  36.             }
  37.             Debug.Assert(weight >= 0);
  38. #if DEBUG
  39.             if ((index == 0) || (weight == 0))
  40.             {
  41.                 Debug.Assert(DP_Memoization_Max_Value_Cache[index][weight] == 0);
  42.             }
  43. #endif
  44.             //value is cached, so return
  45.             if(DP_Memoization_Max_Value_Cache[index][weight] != null)
  46.             {
  47.                 return DP_Memoization_Max_Value_Cache[index][weight].Value;
  48.             }
  49.             Debug.Assert(index > 0);
  50.             Debug.Assert(weight > 0);
  51.             int maxValueWithoutIncludingCurrentItem = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive
  52.                 (weights, values, index - 1, weight, DP_Memoization_Max_Value_Cache);
  53.             if (weights[index-1] > weight)
  54.             {
  55.                 DP_Memoization_Max_Value_Cache[index][weight] = maxValueWithoutIncludingCurrentItem;
  56.                 //current item weight is more, so we cant include - so, just return
  57.                 return maxValueWithoutIncludingCurrentItem;
  58.             }
  59.             int overallMaxValue = maxValueWithoutIncludingCurrentItem;
  60.             int maxValueIncludingCurrentItem = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive
  61.                 (weights, values, index - 1, weight - weights[index-1],
  62.                     DP_Memoization_Max_Value_Cache) + values[index - 1];
  63.             if(maxValueIncludingCurrentItem > overallMaxValue)
  64.             {
  65.                 overallMaxValue = maxValueIncludingCurrentItem;
  66.             }
  67.             DP_Memoization_Max_Value_Cache[index][weight] = overallMaxValue;
  68.             return overallMaxValue;
  69.         }
  70.         

Bottom Up (Tabular) - Eager approach

Code Snippet
  1. public int Knapsack_0_1_DP_Tabular_Bottom_Up(int[] weights, int[] values, int maxWeight)
  2.         {
  3.             this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
  4.             int[][] DP_Tabular_Eager_Max_Value_Cache = new int[values.Length + 1][];
  5.             for (int i = 0; i <= values.Length; i++)
  6.             {
  7.                 DP_Tabular_Eager_Max_Value_Cache[i] = new int[maxWeight + 1];
  8.                 for (int j = 0; j <= maxWeight; j++)
  9.                 {
  10.                     DP_Tabular_Eager_Max_Value_Cache[i][j] = 0; //yes, its default -
  11.                 }
  12.             }
  13.             /// f(i, w) = f(i-1, w) if Wi > w
  14.                      ///Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
  15.                      ///Or 0 if i < 0
  16.             for(int i = 1; i<=values.Length; i++)
  17.             {
  18.                 for(int w = 1; w <= maxWeight; w++)
  19.                 {
  20.                     //below code can be refined - intentional as i just want it
  21.                     //look similar to other 2 versions (top_to_bottom_momoization
  22.                     //and recursive_without_resuing_subproblem_solution
  23.                     int maxValueWithoutIncludingCurrentItem =
  24.                             DP_Tabular_Eager_Max_Value_Cache[i - 1][w];
  25.                     if (weights[i - 1] > w)
  26.                     {
  27.                         DP_Tabular_Eager_Max_Value_Cache[i][w] = maxValueWithoutIncludingCurrentItem;
  28.                     }
  29.                     else
  30.                     {
  31.                         int maxValueByIncludingCurrentItem =
  32.                             DP_Tabular_Eager_Max_Value_Cache[i - 1][w - weights[i - 1]]
  33.                             + values[i-1];
  34.                         int overAllMax = maxValueWithoutIncludingCurrentItem;
  35.                         if(maxValueByIncludingCurrentItem > overAllMax)
  36.                         {
  37.                             overAllMax = maxValueByIncludingCurrentItem;   
  38.                         }
  39.                         DP_Tabular_Eager_Max_Value_Cache[i][w] = overAllMax;
  40.                     }
  41.                 }
  42.             }
  43.             return DP_Tabular_Eager_Max_Value_Cache[values.Length][maxWeight];
  44.         }

Recursion which has optimal sub structure and overlapping sub problems

Code Snippet
  1. public int Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(int[] weights, int[] values, int maxWeight)
  2.         {
  3.             this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
  4.             int v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights, values, index: weights.Length-1, weight: maxWeight);
  5.             return v;
  6.         }
  7.         /// <summary>
  8.         /// f(i, w) = f(i-1, w) if Wi > w
  9.                  ///Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
  10.                  ///Or 0 if i < 0
  11.         /// </summary>
  12.         int Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(int[] weights, int[] values, int index, int weight)
  13.         {
  14.             if (index < 0)
  15.             {
  16.                 return 0;
  17.             }
  18.             Debug.Assert(weight >= 0);
  19.             int maxValueWithoutIncludingCurrentItem = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights,
  20.                 values, index - 1, weight);
  21.             if(weights[index] > weight)
  22.             {
  23.                 //current item weight is more, so we cant include - so, just return
  24.                 return maxValueWithoutIncludingCurrentItem;
  25.             }
  26.             int overallMaxValue = maxValueWithoutIncludingCurrentItem;
  27.             int maxValueIncludingCurrentItem = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights,
  28.                 values, index - 1, weight - weights[index]) + values[index];
  29.             if(maxValueIncludingCurrentItem > overallMaxValue)
  30.             {
  31.                 overallMaxValue = maxValueIncludingCurrentItem;
  32.             }
  33.             return overallMaxValue;
  34.         }

Another recursive method which is also Brute Force

(but note that this recursive method don't have above properties - optimal substructure and overlapping solutions)

Code Snippet
  1. private int _maxValue = int.MinValue;
  2.         private int[] _valueIndices = null;
  3.         public void Knapsack_0_1_BruteForce_2_Power_N(int[] weights, int[] values, int maxWeight)
  4.         {
  5.             this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
  6.             this._maxValue = int.MinValue;
  7.             this._valueIndices = null;
  8.             this.Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, 0, 0, 0, new List<int>());
  9.         }
  10.         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)
  11.         {
  12.             if(currentWeight > maxWeight)
  13.             {
  14.                 return;
  15.             }
  16.             if(currentValue > this._maxValue)
  17.             {
  18.                 this._maxValue = currentValue;
  19.                 this._valueIndices = currentValueIndices.ToArray();
  20.             }
  21.             if(index == weights.Length)
  22.             {
  23.                 return;
  24.             }
  25.             Debug.Assert(index < weights.Length);
  26.             var w = weights[index];
  27.             var v = values[index];
  28.             //see if the current value, conributes to max value
  29.             currentValueIndices.Add(index);
  30.             Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, index + 1, currentWeight + w,
  31.                 currentValue + v, currentValueIndices);
  32.             currentValueIndices.Remove(index);
  33.             //see if current value, does not contribute to max value
  34.             Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, index + 1, currentWeight, currentValue,
  35.                 currentValueIndices);
  36.         }
  37.         private void ValidataInput_Knapsack_0_1(int[] weights, int[] values, int maxWeight)
  38.         {
  39.             #region inputvalidations
  40.             weights.ThrowIfNull("weights");
  41.             values.ThrowIfNull("values");
  42.             weights.Throw("weights", w => (w.Length == 0)
  43.                                   || w.Any(wi => wi < 0));
  44.             values.Throw("values", v => (v.Length == 0)
  45.                                   || v.Any(vi => vi < 0)
  46.                                   || (v.Length != weights.Length));
  47.             maxWeight.Throw("maxWeight", mw => mw <= 0);
  48.             #endregion
  49.         }

Unit Tests

Code Snippet
  1. [TestCategory(Constants.DynamicProgramming)]
  2.         [TestMethod]
  3.         public void Knapsack_0_1_Tests()
  4.         {
  5.             int[] benefits = new int[] { 60, 100, 120 };
  6.             int[] weights = new int[] { 10, 20, 30 };
  7.             this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 50);
  8.             Assert.IsTrue(this._maxValue == 220);
  9.             int v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights,
  10.                 values: benefits, maxWeight: 50);
  11.             Assert.IsTrue(v == 220);
  12.             v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
  13.                 values: benefits, maxWeight: 50);
  14.             Assert.IsTrue(v == 220);
  15.             v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
  16.                 values: benefits, maxWeight: 50);
  17.             Assert.IsTrue(v == 220);
  18.             benefits = new int[] { 3, 4, 5, 8, 10 };
  19.             weights = new int[] { 2, 3, 4, 5, 9 };
  20.             this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 20);
  21.             Assert.IsTrue(this._maxValue == 26);
  22.             v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights, values: benefits,
  23.                 maxWeight: 20);
  24.             Assert.IsTrue(v == 26);
  25.             v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
  26.                 values: benefits, maxWeight: 20);
  27.             Assert.IsTrue(v == 26);
  28.             v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
  29.                 values: benefits, maxWeight: 20);
  30.             Assert.IsTrue(v == 26);
  31.             benefits = new int[] { 3, 4, 5, 6};
  32.             weights = new int[] { 2, 3, 4, 5 };
  33.             this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 5);
  34.             Assert.IsTrue(this._maxValue == 7);
  35.             v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights, values: benefits,
  36.                 maxWeight: 5);
  37.             Assert.IsTrue(v == 7);
  38.             v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
  39.                 values: benefits, maxWeight: 5);
  40.             Assert.IsTrue(v == 7);
  41.             v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
  42.                 values: benefits, maxWeight: 5);
  43.             Assert.IsTrue(v == 7);
  44.         }
Code Snippet
  1. [TestCategory(Constants.DynamicProgramming)]
  2.         [TestMethod]
  3.         public void Knapsack_0_1_Brute_Force_Tests()
  4.         {
  5.             int[] benefits = new int[] { 60, 100, 120 };
  6.             int[] weights = new int[] { 10, 20, 30 };
  7.             this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 50);
  8.             Assert.IsTrue(this._maxValue == 220);
  9.             Assert.IsTrue(this._valueIndices.Contains(1));
  10.             Assert.IsTrue(this._valueIndices.Contains(2));
  11.             Assert.IsTrue(this._valueIndices.Length == 2);
  12.             this._maxValue = int.MinValue;
  13.             this._valueIndices = null;
  14.             benefits = new int[] { 3, 4, 5, 8, 10 };
  15.             weights = new int[] { 2, 3, 4, 5, 9 };
  16.             this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 20);
  17.             Assert.IsTrue(this._maxValue == 26);
  18.             Assert.IsTrue(this._valueIndices.Contains(0));
  19.             Assert.IsTrue(this._valueIndices.Contains(2));
  20.             Assert.IsTrue(this._valueIndices.Contains(3));
  21.             Assert.IsTrue(this._valueIndices.Contains(4));
  22.             Assert.IsTrue(this._valueIndices.Length == 4);
  23.         }

No comments:

Post a Comment