Thursday, August 7, 2014

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
  1. public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum)
  2.         {
  3.             coins.ThrowIfNull("coins");
  4.             coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
  5.             sum.Throw("sum", s => s <= 0);
  6.             int[][] DP_Cache = new int[coins.Length + 1][];
  7.             for (int i = 0; i <= coins.Length; i++)
  8.             {
  9.                 DP_Cache[i] = new int[sum + 1];
  10.             }
  11.             for(int i = 1;i<=coins.Length;i++)
  12.             {
  13.                 for(int s=0;s<=sum;s++)
  14.                 {
  15.                     if (coins[i - 1] == s)
  16.                     {
  17.                         //k, we can get to sum using just the current coin
  18.                         //so, assign to 1, no need to process further
  19.                         DP_Cache[i][s] = 1;
  20.                     }
  21.                     else
  22.                     {
  23.                         //initialize the value withouth the current value
  24.                         int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s];
  25.                         DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I;
  26.                         if ((s > coins[i - 1]) //current coin can particiapte
  27.                             && (DP_Cache[i][s - coins[i - 1]] != 0))
  28.                         {
  29.                             int noOfCoinsUsedIncludingCurrentCoin_I =
  30.                                 DP_Cache[i][s - coins[i - 1]] + 1;
  31.                             if (minNoOfCounsWithoutUsingCurrentCoin_I == 0)
  32.                             {
  33.                                 //so far we couldnt identify coins that sums to 's'
  34.                                 DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I;
  35.                             }
  36.                             else
  37.                             {   
  38.                                 int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I,
  39.                                     minNoOfCounsWithoutUsingCurrentCoin_I);
  40.                                 DP_Cache[i][s] = min;
  41.                             }
  42.                         }
  43.                     }
  44.                 }
  45.             }
  46.             return DP_Cache[coins.Length][sum];
  47.         }

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
  1. public int DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(int[] a, int sum)
  2.         {
  3.             a.ThrowIfNull("a");
  4.             int[][] DP_Memoization = new int[a.Length][];
  5.             for (int i = 0; i < a.Length; i++)
  6.             {
  7.                 DP_Memoization[i] = new int[sum + 1];
  8.                 for (int s = 0; s <= sum; s++)
  9.                 {
  10.                     DP_Memoization[i][s] = -1;
  11.                 }
  12.             }
  13.             var r = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, a.Length-1, sum, DP_Memoization);
  14.             return r;
  15.         }
  16.  
  17.         private int DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(int[] a, int i, int sum, int[][] DP_Memoization)
  18.         {
  19.             if(sum <= 0)
  20.             {
  21.                 return 0;
  22.             }
  23.             if(i < 0)
  24.             {
  25.                 return 0;
  26.             }
  27.             if(DP_Memoization[i][sum] != -1)
  28.             {
  29.                 return DP_Memoization[i][sum];
  30.             }
  31.             int noOfWays = 0;
  32.             //finding the number of ways without including current item
  33.             noOfWays += this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, i - 1, sum, DP_Memoization);
  34.             if(a[i] == sum)
  35.             {
  36.                 noOfWays++;
  37.             }
  38.             if(sum > a[i])
  39.             {
  40.                 noOfWays += this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, i, sum - a[i], DP_Memoization);
  41.             }
  42.             DP_Memoization[i][sum] = noOfWays;
  43.             return noOfWays;
  44.         }

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
  1. public bool DP_CoinChange_SubsetSumWithRep(int[] coins, int sum)
  2.         {
  3.             coins.ThrowIfNull("coins");
  4.             coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
  5.             sum.Throw("sum", s => s <= 0);
  6.             bool[][] DP_Cache = new bool[coins.Length+1][];
  7.             for(int i=0;i<=coins.Length;i++)
  8.             {
  9.                 DP_Cache[i] = new bool[sum + 1];
  10.             }
  11.             for(int i =1;i<=coins.Length;i++)
  12.             {
  13.                 for(int s=0;s<=sum;s++)
  14.                 {
  15.                     DP_Cache[i][s] = (coins[i-1] == s)
  16.                         || DP_Cache[i - 1][s];
  17.                     if(!DP_Cache[i][s]
  18.                         && (s > coins[i-1]))
  19.                     {
  20.                         DP_Cache[i][s] = DP_Cache[i][s - coins[i-1]];
  21.                     }
  22.                 }
  23.             }
  24.             return DP_Cache[coins.Length][sum];
  25.         }
Code Snippet
  1. public bool DoesSubsetSumExistWithRepetition(int[] a, int sum)
  2.         {
  3.             a.ThrowIfNull("a");
  4.             bool f = this.DoesSubsetSumExistWithRepetition(a, a.Length - 1, sum);
  5.             return f;
  6.         }
  7.         public bool DoesSubsetSumExistWithRepetition(int[] a, int index, int sum)
  8.         {
  9.             if(index < 0)
  10.             {
  11.                 return false;
  12.             }
  13.             if(a[index] == sum)
  14.             {
  15.                 return true;
  16.             }
  17.             bool f = this.DoesSubsetSumExistWithRepetition(a, index - 1, sum);
  18.             if(f)
  19.             {
  20.                 return f;
  21.             }
  22.             if(sum > a[index])
  23.             {
  24.                 f = this.DoesSubsetSumExistWithRepetition(a, index, sum - a[index]);
  25.                 return f;
  26.             }
  27.             return false;
  28.         }

Getting unique subsets that sums up-to given sum

Code Snippet
  1. public int[][] GetUniqueSubsetSumPathsWithRepetition(int[] a, int sum)
  2.         {
  3.             a.ThrowIfNull("a");
  4.             var r = this.GetUniqueSubsetSumPathsWithRepetition(a, a.Length - 1, sum);
  5.             return r;
  6.         }
  7.         private int[][] GetUniqueSubsetSumPathsWithRepetition(int[] a, int index, int sum)
  8.         {
  9.             if (index < 0)
  10.             {
  11.                 return new int[0][];
  12.             }
  13.             List<int[]> paths = new List<int[]>();
  14.             if (a[index] == sum)
  15.             {
  16.                 paths.Add(new int[1] { index });
  17.             }
  18.             var p1 = this.GetUniqueSubsetSumPathsWithRepetition(a, index - 1, sum);
  19.             paths.AddRange(p1);
  20.             if (sum > a[index])
  21.             {
  22.                 var p2 = this.GetUniqueSubsetSumPathsWithRepetition(a, index, sum - a[index]);
  23.                 paths.AddRange(this.MergePaths(p2, index));
  24.             }
  25.             return paths.ToArray();
  26.         }
  27.         private int[][] MergePaths(int[][] paths,
  28.             int index)
  29.         {
  30.             Assert.IsNotNull(paths);
  31.             int[][] mergedPaths = new int[paths.Length][];
  32.             Assert.IsTrue(paths.All(p => p.Length > 0));
  33.             for (int i = 0; i < paths.Length; i++)
  34.             {
  35.                 List<int> mergedPath = new List<int>();
  36.                 mergedPath.AddRange(paths[i]);
  37.                 mergedPath.Add(index);
  38.                 mergedPaths[i] = mergedPath.ToArray();
  39.             }
  40.             return mergedPaths;            
  41.         }

Unit Tests

Code Snippet
  1. [TestCategory(Constants.DynamicProgramming)]
  2.         [TestMethod]
  3.         public void SubsetSumWithRepetition_CoinChange_Tests()
  4.         {
  5.             int[] a = new int[] { 2, 3, 6, 7 };
  6.             bool f = this.DoesSubsetSumExistWithRepetition(a, 7);
  7.             Assert.IsTrue(f);
  8.             f = this.DP_CoinChange_SubsetSumWithRep(a, 7);
  9.             Assert.IsTrue(f);
  10.             var p = this.GetUniqueSubsetSumPathsWithRepetition(a, 7);
  11.             Assert.AreEqual(2, p.Length);
  12.             int noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 7);
  13.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
  14.             int min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
  15.             Assert.AreEqual(1, min);
  16.             a = new int[] { 1, 2, 5 };
  17.             f = this.DoesSubsetSumExistWithRepetition(a, 7);
  18.             Assert.IsTrue(f);
  19.             f = this.DP_CoinChange_SubsetSumWithRep(a, 7);
  20.             Assert.IsTrue(f);
  21.             p = this.GetUniqueSubsetSumPathsWithRepetition(a, 7);
  22.             Assert.AreEqual(6, p.Length);
  23.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 7);
  24.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
  25.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
  26.             Assert.AreEqual(2, min);
  27.             a = new int[] { 1, 2 };
  28.             f = this.DoesSubsetSumExistWithRepetition(a, 6);
  29.             Assert.IsTrue(f);
  30.             f = this.DP_CoinChange_SubsetSumWithRep(a, 6);
  31.             Assert.IsTrue(f);
  32.             p = this.GetUniqueSubsetSumPathsWithRepetition(a, 6);
  33.             Assert.AreEqual(4, p.Length);
  34.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 6);
  35.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
  36.             a = new int[] { 4, 3, 2, 2, 1, 1 };
  37.             a = a.Distinct().ToArray();
  38.             f = this.DoesSubsetSumExistWithRepetition(a, 4);
  39.             Assert.IsTrue(f);
  40.             f = this.DP_CoinChange_SubsetSumWithRep(a, 4);
  41.             Assert.IsTrue(f);
  42.             p = this.GetUniqueSubsetSumPathsWithRepetition(a, 4);
  43.             Assert.AreEqual(5, p.Length);
  44.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 4);
  45.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
  46.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 4);
  47.             Assert.AreEqual(1, min);
  48.             a = new int[] { 11, 12, 13 };
  49.             f = this.DoesSubsetSumExistWithRepetition(a, 4);
  50.             Assert.IsFalse(f);
  51.             f = this.DP_CoinChange_SubsetSumWithRep(a, 4);
  52.             Assert.IsFalse(f);
  53.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
  54.             Assert.AreEqual(0, min);
  55.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 13);
  56.             Assert.AreEqual(1, min);
  57.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 37);
  58.             Assert.AreEqual(3, min);
  59.             a = new int[] { 4, 3, 1 };
  60.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 6);
  61.             Assert.AreEqual(2, min);
  62.             a = new int[] { 1, 2, 3 };
  63.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 4);
  64.             Assert.AreEqual(2, min);
  65.             a = new int[] { 1, 2, 4 };
  66.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 5);
  67.             Assert.AreEqual(4, noOfWaysToGetCoinChange);
  68.         }

No comments:

Post a Comment