Dynamic programming - Revision history

217.12.128.228: /* Pseudocode implementation */

2016-02-09T14:38:51Z

‎Pseudocode implementation

41.235.72.105: /* Optimization example: Change problem */

2015-12-30T00:45:25Z

‎Optimization example: Change problem

41.235.72.105: /* Optimization example: Change problem */

2015-12-30T00:43:28Z

‎Optimization example: Change problem

41.235.72.105: /* Optimization example: Change problem */

2015-12-30T00:32:58Z

‎Optimization example: Change problem

41.235.72.105: /* Optimization example: Change problem */

2015-12-29T23:51:41Z

‎Optimization example: Change problem

41.235.72.105: /* Optimization example: Change problem */

2015-12-29T23:51:14Z

‎Optimization example: Change problem

41.235.72.105: /* Optimization example: Change problem */

2015-12-29T23:47:46Z

‎Optimization example: Change problem

41.235.72.105: /* Optimization example: Change problem */

2015-12-29T23:35:40Z

‎Optimization example: Change problem

41.235.72.105: /* Optimization example: Change problem */

2015-12-29T23:34:20Z

‎Optimization example: Change problem

Brian: /* Optimization example: Change problem */ - fixed bug

2015-05-14T23:05:52Z

‎Optimization example: Change problem: - fixed bug

@@ Line 149: / Line 149: @@
      while x[i] - x[j] < A    // x_j is too close
          j = j - 1
-     while x[i] - x[j] &ge; B
+     while x[i] - x[j] &le; B
          dp[i] = dp[i] + dp[j]
          j = j - 1

@@ Line 78: / Line 78: @@
 This problem exhibits optimal substructure in the following sense. Suppose we have found out how to make change for <math>n</math> cents using some minimal collection of coins, and we take one coin away (with value <math>x</math>), leaving a collection of coins with total value <math>n-x</math>. Then, what we are left with ''must'' be an optimal way to make change for <math>n-x</math>. This is because if we had any ''better'' way (fewer coins) of making change for <math>n-x</math>, then we could just add the coin of value <math>x</math> back in, and get a better way of making change for <math>n</math> cents than what we originally assumed was minimal, a contradiction.
-For example, if we have 48 cents in the form of one 25-cent coin, one 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with one 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 6 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling 25 cents) and get a better way. Whenever we have a suboptimal solution to a subinstance, we will also have a suboptimal solution to the original instance; so an optimal solution to the original instance is only allowed to contain optimal solutions to subinstances.
+For example, if we have 48 cents in the form of one 25-cent coin, one 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with one 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 6 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling 48 cents) and get a better way. Whenever we have a suboptimal solution to a subinstance, we will also have a suboptimal solution to the original instance; so an optimal solution to the original instance is only allowed to contain optimal solutions to subinstances.
 To solve the change problem using DP, we start by considering the simplest possible case: when the amount to be changed is zero. Then, the optimal (and only) solution is to use no coins at all. But whenever we change a positive amount, we must use at least one coin. If we take any coin (with value <math>x</math>) away from the optimal change for amount <math>n</math>, then we are left with optimal change for <math>n-x</math>. This implies that we can make optimal change for <math>n</math> using at least one of the following ways: make optimal change for <math>n-d_1</math> and add one coin of value <math>d_1</math>; or make optimal change for <math>n-d_2</math> and add one coin of value <math>d_2</math>; ...; or make optimal change for <math>n-d_m</math> and add one coin of value <math>d_m</math>. This is because if ''none'' of these are optimal, then when we make optimal change for <math>n</math>, and remove some coin of value <math>d_i</math>, leaving <math>n-d_i</math>, we will have optimal change for <math>n-d_i</math>, but we already know that adding a coin of value <math>d_i</math> to the leftover collection does ''not'' give optimal change for <math>n</math>, and yet it regenerates the original collection, which we assumed to be optimal, and this is a contradiction.

@@ Line 78: / Line 78: @@
 This problem exhibits optimal substructure in the following sense. Suppose we have found out how to make change for <math>n</math> cents using some minimal collection of coins, and we take one coin away (with value <math>x</math>), leaving a collection of coins with total value <math>n-x</math>. Then, what we are left with ''must'' be an optimal way to make change for <math>n-x</math>. This is because if we had any ''better'' way (fewer coins) of making change for <math>n-x</math>, then we could just add the coin of value <math>x</math> back in, and get a better way of making change for <math>n</math> cents than what we originally assumed was minimal, a contradiction.
-For example, if we have 48 cents in the form of one 25-cent coin, one 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with two 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 7 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling 25 cents) and get a better way. Whenever we have a suboptimal solution to a subinstance, we will also have a suboptimal solution to the original instance; so an optimal solution to the original instance is only allowed to contain optimal solutions to subinstances.
+For example, if we have 48 cents in the form of one 25-cent coin, one 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with one 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 6 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling 25 cents) and get a better way. Whenever we have a suboptimal solution to a subinstance, we will also have a suboptimal solution to the original instance; so an optimal solution to the original instance is only allowed to contain optimal solutions to subinstances.
 To solve the change problem using DP, we start by considering the simplest possible case: when the amount to be changed is zero. Then, the optimal (and only) solution is to use no coins at all. But whenever we change a positive amount, we must use at least one coin. If we take any coin (with value <math>x</math>) away from the optimal change for amount <math>n</math>, then we are left with optimal change for <math>n-x</math>. This implies that we can make optimal change for <math>n</math> using at least one of the following ways: make optimal change for <math>n-d_1</math> and add one coin of value <math>d_1</math>; or make optimal change for <math>n-d_2</math> and add one coin of value <math>d_2</math>; ...; or make optimal change for <math>n-d_m</math> and add one coin of value <math>d_m</math>. This is because if ''none'' of these are optimal, then when we make optimal change for <math>n</math>, and remove some coin of value <math>d_i</math>, leaving <math>n-d_i</math>, we will have optimal change for <math>n-d_i</math>, but we already know that adding a coin of value <math>d_i</math> to the leftover collection does ''not'' give optimal change for <math>n</math>, and yet it regenerates the original collection, which we assumed to be optimal, and this is a contradiction.

@@ Line 70: / Line 70: @@
 ==Optimization example: Change problem==
-''Dynamic change'' is the name given to a well-known algorithm for determining how to make change for a given amount of money using the fewest possible coins, assuming that we have an unlimited supply of coins of every denomination. For example, if the available denominations are 1 cent, 5 cents, 10 cents, and 25 cents, then we can make change for 48 cents by using one 25-cent coin, two 10-cent coins, and three 1-cent coins, that is, 6 coins in total. There are other ways to make change for the same amount (for example, four 10-cent coins and eight 1-cent coins), but they all use 12 coins. Other sets of denominations are not so easy; for example, suppose we have at our disposal 17-cent, 14-cent, 9-cent, and 7-cent coins. It is now not immediately obvious how best to make change for a dollar (The solution is to use four 17-cent coins, one 14-cent coin, and two 9-cent coins.) Nor is it immediately obvious that it is impossible to make change for 29 cents.
+''Dynamic change'' is the name given to a well-known algorithm for determining how to make change for a given amount of money using the fewest possible coins, assuming that we have an unlimited supply of coins of every denomination. For example, if the available denominations are 1 cent, 5 cents, 10 cents, and 25 cents, then we can make change for 48 cents by using one 25-cent coin, one 10-cent coins, two 5-cent,and three 1-cent coins, that is, 7 coins in total. There are other ways to make change for the same amount (for example, four 10-cent coins and eight 1-cent coins), but they all use 12 coins. Other sets of denominations are not so easy; for example, suppose we have at our disposal 17-cent, 14-cent, 9-cent, and 7-cent coins. It is now not immediately obvious how best to make change for a dollar (The solution is to use four 17-cent coins, one 14-cent coin, and two 9-cent coins.) Nor is it immediately obvious that it is impossible to make change for 29 cents.
 The problem {{Problem|ccc00s4|Golf}} from the 2000 Canadian Computing Competition is exactly analogous. Here, the distance to the hole is the amount for which we wish to make change, and each golf club is a denomination with value equal to how far it will hit the golf ball.
@@ Line 78: / Line 78: @@
 This problem exhibits optimal substructure in the following sense. Suppose we have found out how to make change for <math>n</math> cents using some minimal collection of coins, and we take one coin away (with value <math>x</math>), leaving a collection of coins with total value <math>n-x</math>. Then, what we are left with ''must'' be an optimal way to make change for <math>n-x</math>. This is because if we had any ''better'' way (fewer coins) of making change for <math>n-x</math>, then we could just add the coin of value <math>x</math> back in, and get a better way of making change for <math>n</math> cents than what we originally assumed was minimal, a contradiction.
-For example, if we have 48 cents in the form of one 25-cent coin, two 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with two 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 7 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling 25 cents) and get a better way. Whenever we have a suboptimal solution to a subinstance, we will also have a suboptimal solution to the original instance; so an optimal solution to the original instance is only allowed to contain optimal solutions to subinstances.
+For example, if we have 48 cents in the form of one 25-cent coin, one 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with two 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 7 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling 25 cents) and get a better way. Whenever we have a suboptimal solution to a subinstance, we will also have a suboptimal solution to the original instance; so an optimal solution to the original instance is only allowed to contain optimal solutions to subinstances.
 To solve the change problem using DP, we start by considering the simplest possible case: when the amount to be changed is zero. Then, the optimal (and only) solution is to use no coins at all. But whenever we change a positive amount, we must use at least one coin. If we take any coin (with value <math>x</math>) away from the optimal change for amount <math>n</math>, then we are left with optimal change for <math>n-x</math>. This implies that we can make optimal change for <math>n</math> using at least one of the following ways: make optimal change for <math>n-d_1</math> and add one coin of value <math>d_1</math>; or make optimal change for <math>n-d_2</math> and add one coin of value <math>d_2</math>; ...; or make optimal change for <math>n-d_m</math> and add one coin of value <math>d_m</math>. This is because if ''none'' of these are optimal, then when we make optimal change for <math>n</math>, and remove some coin of value <math>d_i</math>, leaving <math>n-d_i</math>, we will have optimal change for <math>n-d_i</math>, but we already know that adding a coin of value <math>d_i</math> to the leftover collection does ''not'' give optimal change for <math>n</math>, and yet it regenerates the original collection, which we assumed to be optimal, and this is a contradiction.

@@ Line 70: / Line 70: @@
 ==Optimization example: Change problem==
-''Dynamic change'' is the name given to a well-known algorithm for determining how to make change for a given amount of money using the fewest possible coins, assuming that we have an unlimited supply of coins of every denomination. For example, if the available denominations are 1 cent, 5 cents, 10 cents, and 25 cents, then we can make change for 48 cents by using one 25-cent coin, two 10-cent coins, and three 1-cent coins, that is, 6 coins in total. There are other ways to make change for the same amount (for example, four 10-cent coins and eight 1-cent coins), but they all use 12 ؤخهىس. Other sets of denominations are not so easy; for example, suppose we have at our disposal 17-cent, 14-cent, 9-cent, and 7-cent coins. It is now not immediately obvious how best to make change for a dollar (The solution is to use four 17-cent coins, one 14-cent coin, and two 9-cent coins.) Nor is it immediately obvious that it is impossible to make change for 29 cents.
+''Dynamic change'' is the name given to a well-known algorithm for determining how to make change for a given amount of money using the fewest possible coins, assuming that we have an unlimited supply of coins of every denomination. For example, if the available denominations are 1 cent, 5 cents, 10 cents, and 25 cents, then we can make change for 48 cents by using one 25-cent coin, two 10-cent coins, and three 1-cent coins, that is, 6 coins in total. There are other ways to make change for the same amount (for example, four 10-cent coins and eight 1-cent coins), but they all use 12 coins. Other sets of denominations are not so easy; for example, suppose we have at our disposal 17-cent, 14-cent, 9-cent, and 7-cent coins. It is now not immediately obvious how best to make change for a dollar (The solution is to use four 17-cent coins, one 14-cent coin, and two 9-cent coins.) Nor is it immediately obvious that it is impossible to make change for 29 cents.
 The problem {{Problem|ccc00s4|Golf}} from the 2000 Canadian Computing Competition is exactly analogous. Here, the distance to the hole is the amount for which we wish to make change, and each golf club is a denomination with value equal to how far it will hit the golf ball.

@@ Line 93: / Line 93: @@
      c[i] &larr; &infin;
      for j &isin; [1..m]
-         if d[j] &le; c[i]
+         if d[j] &le; i
              c[i] &larr; min(c[i], c[i-d[j]]+1)
 if c[n] = &infin;
@@ Line 108: / Line 108: @@
      c[i] &larr; &infin;
      for j &isin; [1..m]
-         if d[j] &le; c[i]
+         if d[j] &le; i
              if c[i-d[j]]+1 < c[i]
                  c[i] &larr; c[i-d[j]]+1