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

150. public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum)
151.         {
152.             coins.ThrowIfNull("coins");
153.             coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
154.             sum.Throw("sum", s => s <= 0);
155.             int[][] DP_Cache = new int[coins.Length + 1][];
156.             for (int i = 0; i <= coins.Length; i++)
157.             {
158.                 DP_Cache[i] = new int[sum + 1];
159.             }
160.             for(int i = 1;i<=coins.Length;i++)
161.             {
162.                 for(int s=0;s<=sum;s++)
163.                 {
164.                     if (coins[i - 1] == s)
165.                     {
166.                         //k, we can get to sum using just the current coin
167.                         //so, assign to 1, no need to process further
168.                         DP_Cache[i][s] = 1;
169.                     }
170.                     else
171.                     {
172.                         //initialize the value withouth the current value
173.                         int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s];
174.                         DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I;
175.                         if ((s > coins[i - 1]) //current coin can particiapte
176.                             && (DP_Cache[i][s - coins[i - 1]] != 0))
177.                         {
178.                             int noOfCoinsUsedIncludingCurrentCoin_I =
179.                                 DP_Cache[i][s - coins[i - 1]] + 1;
180.                             if (minNoOfCounsWithoutUsingCurrentCoin_I == 0)
181.                             {
182.                                 //so far we couldnt identify coins that sums to 's'
183.                                 DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I;
184.                             }
185.                             else
186.                             {   
187.                                 int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I,
188.                                     minNoOfCounsWithoutUsingCurrentCoin_I);
189.                                 DP_Cache[i][s] = min;
190.                             }
191.                         }
192.                     }
193.                 }
194.             }
195.             return DP_Cache[coins.Length][sum];
196.         }

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

13. public int DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(int[] a, int sum)
14.         {
15.             a.ThrowIfNull("a");
16.             int[][] DP_Memoization = new int[a.Length][];
17.             for (int i = 0; i < a.Length; i++)
18.             {
19.                 DP_Memoization[i] = new int[sum + 1];
20.                 for (int s = 0; s <= sum; s++)
21.                 {
22.                     DP_Memoization[i][s] = -1;
23.                 }
24.             }
25.             var r = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, a.Length-1, sum, DP_Memoization);
26.             return r;
27.         }
28.  
29.         private int DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(int[] a, int i, int sum, int[][] DP_Memoization)
30.         {
31.             if(sum <= 0)
32.             {
33.                 return 0;
34.             }
35.             if(i < 0)
36.             {
37.                 return 0;
38.             }
39.             if(DP_Memoization[i][sum] != -1)
40.             {
41.                 return DP_Memoization[i][sum];
42.             }
43.             int noOfWays = 0;
44.             //finding the number of ways without including current item
45.             noOfWays += this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, i - 1, sum, DP_Memoization);
46.             if(a[i] == sum)
47.             {
48.                 noOfWays++;
49.             }
50.             if(sum > a[i])
51.             {
52.                 noOfWays += this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, i, sum - a[i], DP_Memoization);
53.             }
54.             DP_Memoization[i][sum] = noOfWays;
55.             return noOfWays;
56.         }

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

197. public bool DP_CoinChange_SubsetSumWithRep(int[] coins, int sum)
198.         {
199.             coins.ThrowIfNull("coins");
200.             coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
201.             sum.Throw("sum", s => s <= 0);
202.             bool[][] DP_Cache = new bool[coins.Length+1][];
203.             for(int i=0;i<=coins.Length;i++)
204.             {
205.                 DP_Cache[i] = new bool[sum + 1];
206.             }
207.             for(int i =1;i<=coins.Length;i++)
208.             {
209.                 for(int s=0;s<=sum;s++)
210.                 {
211.                     DP_Cache[i][s] = (coins[i-1] == s)
212.                         || DP_Cache[i - 1][s];
213.                     if(!DP_Cache[i][s]
214.                         && (s > coins[i-1]))
215.                     {
216.                         DP_Cache[i][s] = DP_Cache[i][s - coins[i-1]];
217.                     }
218.                 }
219.             }
220.             return DP_Cache[coins.Length][sum];
221.         }

Code Snippet

117. public bool DoesSubsetSumExistWithRepetition(int[] a, int sum)
118.         {
119.             a.ThrowIfNull("a");
120.             bool f = this.DoesSubsetSumExistWithRepetition(a, a.Length - 1, sum);
121.             return f;
122.         }
123.         public bool DoesSubsetSumExistWithRepetition(int[] a, int index, int sum)
124.         {
125.             if(index < 0)
126.             {
127.                 return false;
128.             }
129.             if(a[index] == sum)
130.             {
131.                 return true;
132.             }
133.             bool f = this.DoesSubsetSumExistWithRepetition(a, index - 1, sum);
134.             if(f)
135.             {
136.                 return f;
137.             }
138.             if(sum > a[index])
139.             {
140.                 f = this.DoesSubsetSumExistWithRepetition(a, index, sum - a[index]);
141.                 return f;
142.             }
143.             return false;
144.         }

Getting unique subsets that sums up-to given sum

Code Snippet

57. public int[][] GetUniqueSubsetSumPathsWithRepetition(int[] a, int sum)
58.         {
59.             a.ThrowIfNull("a");
60.             var r = this.GetUniqueSubsetSumPathsWithRepetition(a, a.Length - 1, sum);
61.             return r;
62.         }
63.         private int[][] GetUniqueSubsetSumPathsWithRepetition(int[] a, int index, int sum)
64.         {
65.             if (index < 0)
66.             {
67.                 return new int[0][];
68.             }
69.             List<int[]> paths = new List<int[]>();
70.             if (a[index] == sum)
71.             {
72.                 paths.Add(new int[1] { index });
73.             }
74.             var p1 = this.GetUniqueSubsetSumPathsWithRepetition(a, index - 1, sum);
75.             paths.AddRange(p1);
76.             if (sum > a[index])
77.             {
78.                 var p2 = this.GetUniqueSubsetSumPathsWithRepetition(a, index, sum - a[index]);
79.                 paths.AddRange(this.MergePaths(p2, index));
80.             }
81.             return paths.ToArray();
82.         }
83.         private int[][] MergePaths(int[][] paths,
84.             int index)
85.         {
86.             Assert.IsNotNull(paths);
87.             int[][] mergedPaths = new int[paths.Length][];
88.             Assert.IsTrue(paths.All(p => p.Length > 0));
89.             for (int i = 0; i < paths.Length; i++)
90.             {
91.                 List<int> mergedPath = new List<int>();
92.                 mergedPath.AddRange(paths[i]);
93.                 mergedPath.Add(index);
94.                 mergedPaths[i] = mergedPath.ToArray();
95.             }
96.             return mergedPaths;            
97.         }

Unit Tests

Code Snippet

202. [TestCategory(Constants.DynamicProgramming)]
203.         [TestMethod]
204.         public void SubsetSumWithRepetition_CoinChange_Tests()
205.         {
206.             int[] a = new int[] { 2, 3, 6, 7 };
207.             bool f = this.DoesSubsetSumExistWithRepetition(a, 7);
208.             Assert.IsTrue(f);
209.             f = this.DP_CoinChange_SubsetSumWithRep(a, 7);
210.             Assert.IsTrue(f);
211.             var p = this.GetUniqueSubsetSumPathsWithRepetition(a, 7);
212.             Assert.AreEqual(2, p.Length);
213.             int noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 7);
214.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
215.             int min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
216.             Assert.AreEqual(1, min);
217.             a = new int[] { 1, 2, 5 };
218.             f = this.DoesSubsetSumExistWithRepetition(a, 7);
219.             Assert.IsTrue(f);
220.             f = this.DP_CoinChange_SubsetSumWithRep(a, 7);
221.             Assert.IsTrue(f);
222.             p = this.GetUniqueSubsetSumPathsWithRepetition(a, 7);
223.             Assert.AreEqual(6, p.Length);
224.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 7);
225.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
226.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
227.             Assert.AreEqual(2, min);
228.             a = new int[] { 1, 2 };
229.             f = this.DoesSubsetSumExistWithRepetition(a, 6);
230.             Assert.IsTrue(f);
231.             f = this.DP_CoinChange_SubsetSumWithRep(a, 6);
232.             Assert.IsTrue(f);
233.             p = this.GetUniqueSubsetSumPathsWithRepetition(a, 6);
234.             Assert.AreEqual(4, p.Length);
235.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 6);
236.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
237.             a = new int[] { 4, 3, 2, 2, 1, 1 };
238.             a = a.Distinct().ToArray();
239.             f = this.DoesSubsetSumExistWithRepetition(a, 4);
240.             Assert.IsTrue(f);
241.             f = this.DP_CoinChange_SubsetSumWithRep(a, 4);
242.             Assert.IsTrue(f);
243.             p = this.GetUniqueSubsetSumPathsWithRepetition(a, 4);
244.             Assert.AreEqual(5, p.Length);
245.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 4);
246.             Assert.AreEqual(p.Length, noOfWaysToGetCoinChange);
247.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 4);
248.             Assert.AreEqual(1, min);
249.             a = new int[] { 11, 12, 13 };
250.             f = this.DoesSubsetSumExistWithRepetition(a, 4);
251.             Assert.IsFalse(f);
252.             f = this.DP_CoinChange_SubsetSumWithRep(a, 4);
253.             Assert.IsFalse(f);
254.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 7);
255.             Assert.AreEqual(0, min);
256.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 13);
257.             Assert.AreEqual(1, min);
258.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 37);
259.             Assert.AreEqual(3, min);
260.             a = new int[] { 4, 3, 1 };
261.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 6);
262.             Assert.AreEqual(2, min);
263.             a = new int[] { 1, 2, 3 };
264.             min = this.DP_CoinChange_GetMinimalDemoninations(a, 4);
265.             Assert.AreEqual(2, min);
266.             a = new int[] { 1, 2, 4 };
267.             noOfWaysToGetCoinChange = this.DP_Memoization_GetNumberOfWaysToMakeTheChange_SubsetSumWithRepetition(a, 5);
268.             Assert.AreEqual(4, noOfWaysToGetCoinChange);
269.         }