Programmer

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

 public int Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(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] = null; //yes, its default - just to be defensive
                    if(i == 0)
                    {
                        DP_Memoization_Max_Value_Cache[0][j] = 0;
                    }
                }
                //value for weight zero is zero :)
                DP_Memoization_Max_Value_Cache[i][0] = 0;
            }
            var v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive(weights, values, 
                index: values.Length, weight: maxWeight, 
                DP_Memoization_Max_Value_Cache: DP_Memoization_Max_Value_Cache);
            Assert.IsTrue(v == DP_Memoization_Max_Value_Cache[values.Length][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_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;
        }
        

Bottom Up (Tabular) - Eager approach

Code Snippet

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_Tabular_Eager_Max_Value_Cache = new int[values.Length + 1][];
            for (int i = 0; i <= values.Length; i++)
            {
                DP_Tabular_Eager_Max_Value_Cache[i] = new int[maxWeight + 1];
                for (int j = 0; j <= maxWeight; j++)
                {
                    DP_Tabular_Eager_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_Tabular_Eager_Max_Value_Cache[i - 1][w];
                    if (weights[i - 1] > w)
                    {
                        DP_Tabular_Eager_Max_Value_Cache[i][w] = maxValueWithoutIncludingCurrentItem;
                    }
                    else
                    {
                        int maxValueByIncludingCurrentItem =
                            DP_Tabular_Eager_Max_Value_Cache[i - 1][w - weights[i - 1]]
                            + values[i-1];
                        int overAllMax = maxValueWithoutIncludingCurrentItem;
                        if(maxValueByIncludingCurrentItem > overAllMax)
                        {
                            overAllMax = maxValueByIncludingCurrentItem;   
                        }
                        DP_Tabular_Eager_Max_Value_Cache[i][w] = overAllMax;
                    }
                }
            }
            return DP_Tabular_Eager_Max_Value_Cache[values.Length][maxWeight];
        }

Recursion which has optimal sub structure and overlapping sub problems

Code Snippet

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;
        }

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

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);
        }
        private void ValidataInput_Knapsack_0_1(int[] weights, int[] values, int maxWeight)
        {
            #region inputvalidations
            weights.ThrowIfNull("weights");
            values.ThrowIfNull("values");
            weights.Throw("weights", w => (w.Length == 0)
                                  || w.Any(wi => wi < 0));
            values.Throw("values", v => (v.Length == 0)
                                  || v.Any(vi => vi < 0)
                                  || (v.Length != weights.Length));
            maxWeight.Throw("maxWeight", mw => mw <= 0);
            #endregion
        }

Unit Tests

Code Snippet

 [TestCategory(Constants.DynamicProgramming)]
        [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);
        }

Code Snippet

 [TestCategory(Constants.DynamicProgramming)]
        [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);
        }

Coin Change (subset sum problem with repetition) - III

This is basically follow-up to previous post where subset sum problem without repetition has been discussed.

1. What are the minimum no. of coins required to get to the given target? (nothing but one of the variations of subset sum problem with repetition)

Say, f[i, sum] finds the minimum no. of coins required to get to 'sum' by using given coins up-to ith index
                  f[i, w] = 0 if i<= 0
                                0 if sum < 0
                                1 if sum == weights[i]
                                f[i-1, w] if weights[i] > w
                                f[i-1, w] if f(i, w-weights[i]) == 0
                                f(i, w-weighs[i]) + 1 if f[i-1, w] == 0
                                min (f(i-1, w), f(i, w-weighs[i]) + 1)

Below is the corresponding code...

Code Snippet

public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum)
        {
            coins.ThrowIfNull("coins");
            coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
            sum.Throw("sum", s => s <= 0);
            int[][] DP_Cache = new int[coins.Length + 1][];
            for (int i = 0; i <= coins.Length; i++)
            {
                DP_Cache[i] = new int[sum + 1];
            }
            for(int i = 1;i<=coins.Length;i++)
            {
                for(int s=0;s<=sum;s++)
                {
                    if (coins[i - 1] == s)
                    {
                        //k, we can get to sum using just the current coin
                        //so, assign to 1, no need to process further
                        DP_Cache[i][s] = 1;
                    }
                    else 
                    {
                        //initialize the value withouth the current value
                        int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s];
                        DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I;
                        if ((s > coins[i - 1]) //current coin can particiapte
                            && (DP_Cache[i][s - coins[i - 1]] != 0))
                        {
                            int noOfCoinsUsedIncludingCurrentCoin_I = 
                                DP_Cache[i][s - coins[i - 1]] + 1;
                            if (minNoOfCounsWithoutUsingCurrentCoin_I == 0)
                            {
                                //so far we couldnt identify coins that sums to 's'
                                DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I;
                            }
                            else
                            {   
                                int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I, 
                                    minNoOfCounsWithoutUsingCurrentCoin_I);
                                DP_Cache[i][s] = min;
                            }
                        }
                    }
                }
            }
            return DP_Cache[coins.Length][sum];
        }

Total number of ways to make the change

Say, f[i, sum] represents total number of ways to make the change by using upto 'i' coins (coins can be used repeatedly) then,

          f[i, sum] = 0   if i<= 0
                            0 if sum < 0
                            1 if sum == 0
                            f[i-1, sum] + f[i, sum-weights[i]]

Another way to define the same is by,
           f[i, sum] = 0 if i <=0
                             f[i-1, sum] + 1 if weights[i] == sum
                             f[i-1, sum] if weights[i] > sum
                             f[i-1, sum] + f[i, sum-weights[i]]

Below is the corresponding code...

Code Snippet

public int DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(int[] a, int sum)
        {
            a.ThrowIfNull("a");
            int[][] DP_Memoization = new int[a.Length][];
            for (int i = 0; i < a.Length; i++)
            {
                DP_Memoization[i] = new int[sum + 1];
                for (int s = 0; s <= sum; s++)
                {
                    DP_Memoization[i][s] = -1;
                }
            }
            var r = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, a.Length-1, sum, DP_Memoization);
            return r;
        }
 
        private int DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(int[] a, int i, int sum, int[][] DP_Memoization)
        {
            if(sum <= 0)
            {
                return 0;
            }
            if(i < 0)
            {
                return 0;
            }
            if(DP_Memoization[i][sum] != -1)
            {
                return DP_Memoization[i][sum];
            }
            int noOfWays = 0;
            //finding the number of ways without including current item
            noOfWays += this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, i - 1, sum, DP_Memoization);
            if(a[i] == sum)
            {
                noOfWays++;
            }
            if(sum > a[i])
            {
                noOfWays += this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, i, sum - a[i], DP_Memoization);
            }
            DP_Memoization[i][sum] = noOfWays;
            return noOfWays;
        }

Decision making - finding whether its possible to get the coin change

f[i, sum] = False if i<=0
                  False if sum < 0
                  True if sum == 0
                  f[i-1, sum] || [i, sum-weights[i]]

Or, f[i, sum] = False if i<= 0
                        True if weights[i] == sum
                        f[i-1, w] if weights[i] > sum
                        f[i-1, w] || f[i, w- weights[i]]

Below is the corresponding code...

Code Snippet

public bool DP_CoinChange_SubsetSumWithRep(int[] coins, int sum)
        {
            coins.ThrowIfNull("coins");
            coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
            sum.Throw("sum", s => s <= 0);
            bool[][] DP_Cache = new bool[coins.Length+1][];
            for(int i=0;i<=coins.Length;i++)
            {
                DP_Cache[i] = new bool[sum + 1];
            }
            for(int i =1;i<=coins.Length;i++)
            {
                for(int s=0;s<=sum;s++)
                {
                    DP_Cache[i][s] = (coins[i-1] == s)
                        || DP_Cache[i - 1][s];
                    if(!DP_Cache[i][s]
                        && (s > coins[i-1]))
                    {
                        DP_Cache[i][s] = DP_Cache[i][s - coins[i-1]];
                    }
                }
            }
            return DP_Cache[coins.Length][sum];
        }

Code Snippet

public bool DoesSubsetSumExistWithRepetition(int[] a, int sum)
        {
            a.ThrowIfNull("a");
            bool f = this.DoesSubsetSumExistWithRepetition(a, a.Length - 1, sum);
            return f;
        }
        public bool DoesSubsetSumExistWithRepetition(int[] a, int index, int sum)
        {
            if(index < 0)
            {
                return false;
            }
            if(a[index] == sum)
            {
                return true;
            }
            bool f = this.DoesSubsetSumExistWithRepetition(a, index - 1, sum);
            if(f)
            {
                return f;
            }
            if(sum > a[index])
            {
                f = this.DoesSubsetSumExistWithRepetition(a, index, sum - a[index]);
                return f;
            }
            return false;
        }

Getting unique subsets that sums up-to given sum

Code Snippet

public int[][] GetUniqueSubsetSumPathsWithRepetition(int[] a, int sum)
        {
            a.ThrowIfNull("a");
            var r = this.GetUniqueSubsetSumPathsWithRepetition(a, a.Length - 1, sum);
            return r;
        }
        private int[][] GetUniqueSubsetSumPathsWithRepetition(int[] a, int index, int sum)
        {
            if (index < 0)
            {
                return new int[0][];
            }
            List<int[]> paths = new List<int[]>();
            if (a[index] == sum)
            {
                paths.Add(new int[1] { index });
            }
            var p1 = this.GetUniqueSubsetSumPathsWithRepetition(a, index - 1, sum);
            paths.AddRange(p1);
            if (sum > a[index])
            {
                var p2 = this.GetUniqueSubsetSumPathsWithRepetition(a, index, sum - a[index]);
                paths.AddRange(this.MergePaths(p2, index));
            }
            return paths.ToArray();
        }
        private int[][] MergePaths(int[][] paths,
            int index)
        {
            Assert.IsNotNull(paths);
            int[][] mergedPaths = new int[paths.Length][];
            Assert.IsTrue(paths.All(p => p.Length > 0));
            for (int i = 0; i < paths.Length; i++)
            {
                List<int> mergedPath = new List<int>();
                mergedPath.AddRange(paths[i]);
                mergedPath.Add(index);
                mergedPaths[i] = mergedPath.ToArray();
            }
            return mergedPaths;            
        }

Unit Tests

Code Snippet

[TestCategory(Constants.DynamicProgramming)]
        [TestMethod]
        public void SubsetSumWithRepetition_CoinChange_Tests()
        {
            int[] a = new int[] { 2, 3, 6, 7 };
            bool f = this.DoesSubsetSumExistWithRepetition(a, 7);
            Assert.IsTrue(f);
            f = this.DP_CoinChange_SubsetSumWithRep(a, 7);
            Assert.IsTrue(f);
            var p = this.GetUniqueSubsetSumPathsWithRepetition(a, 7);
            Assert.AreEqual(2, p.Length);
            int noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 7);
            Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
            int min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
            Assert.AreEqual(1, min);
            a = new int[] { 1, 2, 5 };
            f = this.DoesSubsetSumExistWithRepetition(a, 7);
            Assert.IsTrue(f);
            f = this.DP_CoinChange_SubsetSumWithRep(a, 7);
            Assert.IsTrue(f);
            p = this.GetUniqueSubsetSumPathsWithRepetition(a, 7);
            Assert.AreEqual(6, p.Length);
            noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 7);
            Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
            min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
            Assert.AreEqual(2, min);
            a = new int[] { 1, 2 };
            f = this.DoesSubsetSumExistWithRepetition(a, 6);
            Assert.IsTrue(f);
            f = this.DP_CoinChange_SubsetSumWithRep(a, 6);
            Assert.IsTrue(f);
            p = this.GetUniqueSubsetSumPathsWithRepetition(a, 6);
            Assert.AreEqual(4, p.Length);
            noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 6);
            Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
            a = new int[] { 4, 3, 2, 2, 1, 1 };
            a = a.Distinct().ToArray();
            f = this.DoesSubsetSumExistWithRepetition(a, 4);
            Assert.IsTrue(f);
            f = this.DP_CoinChange_SubsetSumWithRep(a, 4);
            Assert.IsTrue(f);
            p = this.GetUniqueSubsetSumPathsWithRepetition(a, 4);
            Assert.AreEqual(5, p.Length);
            noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 4);
            Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
            min = this.DP_CoinChange_GetMinimalDemoninations(a, 4);
            Assert.AreEqual(1, min);
            a = new int[] { 11, 12, 13 };
            f = this.DoesSubsetSumExistWithRepetition(a, 4);
            Assert.IsFalse(f);
            f = this.DP_CoinChange_SubsetSumWithRep(a, 4);
            Assert.IsFalse(f);
            min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
            Assert.AreEqual(0, min);
            min = this.DP_CoinChange_GetMinimalDemoninations(a, 13);
            Assert.AreEqual(1, min);
            min = this.DP_CoinChange_GetMinimalDemoninations(a, 37);
            Assert.AreEqual(3, min);
            a = new int[] { 4, 3, 1 };
            min = this.DP_CoinChange_GetMinimalDemoninations(a, 6);
            Assert.AreEqual(2, min);
            a = new int[] { 1, 2, 3 };
            min = this.DP_CoinChange_GetMinimalDemoninations(a, 4);
            Assert.AreEqual(2, min);
            a = new int[] { 1, 2, 4 };
            noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 5);
            Assert.AreEqual(4, noOfWaysToGetCoinChange);
        }

Labels

Thursday, August 7, 2014

Knapsack (0/1, unbound) Problem

Knapsack 0/1

Unbound Knapsack

Using Memoization

Bottom Up (Tabular) - Eager approach

Recursion which has optimal sub structure and overlapping sub problems

Another recursive method which is also Brute Force

Unit Tests

Coin Change (subset sum problem with repetition) - III

Total number of ways to make the change

Decision making - finding whether its possible to get the coin change

Getting unique subsets that sums up-to given sum

Unit Tests