Please enable JavaScript.

Coggle requires JavaScript to display documents.

M16-1, : - Coggle Diagram

- - - - Change-making problem
        
        Give change for amount n using the minimum number of coins of denominations d1 < d2 < ... < dm.
        
        Let F (n) be the minimum number of coins whose values add up to n; it is convenient to define F (0) = 0. The amount n can only be obtained by adding one coin of denomination dj to the amount n − dj for j = 1, 2,...,m such that n ≥ dj. Therefore, we can consider all such denominations and select the one minimizing F (n − dj ) + 1. Since 1 is a constant, we can, of course, find the smallest F (n − dj ) first and then add 1 to it.
      - Coin-collecting problem
        
        Several coins are placed in cells of an n × m board, no more than one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it always picks up that coin. Design an algorithm to find the maximum number of coins the robot can collect and a path it needs to follow to do this.
        
        Let F (i, j ) be the largest number of coins the robot can collect and bring to the cell (i, j ) in the ith row and j th column of the board. It can reach this cell either from the adjacent cell (i − 1, j) above it or from the adjacent cell (i, j − 1) to the left of it. The largest numbers of coins that can be brought to these cells
        are F (i − 1,j) and F (i, j − 1), respectively. Of course, there are no adjacent cells above the cells in the first row, and there are no adjacent cells to the left of the cells in the first column. For those cells, we assume that F (i − 1,j) and F (i, j − 1) are equal to 0 for their nonexistent neighbors. Therefore, the largest number of
        coins the robot can bring to cell (i, j ) is the maximum of these two numbers plus one possible coin at cell (i, j ) itself.
      - Coin-row problem
        
        There is a row of n coins whose values are some positive integers c1, c2,...,cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
        
        Let F (n) be the maximum amount that can be picked up from the row of n coins. To derive a recurrence for F (n), we partition all the allowed coin selections into two groups:those that include the last coin and those without it. The largest amount we can get from the first group is equal to cn + F (n − 2)——the value of the nth coin plus the maximum amount we can pick up from the first n − 2 coins. The maximum amount we can get from the second group is equal to F (n − 1) by the definition of F (n).
    - - Given n items of known weights w1,...,wn and values
        v1,...,vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.
        
        Let us consider an instance defined by the
        first i items, 1 ≤ i ≤ n, with weights w1,...,wi, values v1,...,vi, and knapsack capacity j, 1 ≤ j ≤ W. Let F (i, j ) be the value of an optimal solution to this instance, i.e., the value of the most valuable subset of the first i items that fit into the knapsack of capacity j. We can divide all the subsets of the first i items that fit
        the knapsack of capacity j into two categories: those that do not include the ith item and those that do.
        
        Among the subsets that do include the ith item (hence, j − wi ≥ 0), an optimal subset is made up of this item and an optimal subset of the first i − 1 items that fits into the knapsack of capacity j − wi.
        
        Thus, the value of an optimal solution among all feasible subsets of the first i
        items is the maximum of these two values.
        
        Of course, if the ith item does not fit into the knapsack, the value of an optimal subset selected from the first i items is the same as the value of an optimal subset selected from the first i − 1 items.
        
        Among the subsets that do not include the ith item, the value of an optimal subset is, by definition, F (i − 1, j ).