Question

Exercises

15.3-1  Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer.

16.2-2 Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(n W) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack.

Answer 1

15.3. Here, we are running RECURSIVE-MATRIX-CHAIN which is more efficient way to determinate the optimal number of multiplications in a matrix-chain multiplication problem.

We have 2 cases:

First case: Enumeration

• For each possible place to split the matrix chain, the enumeration approach finds all the ways to parenthesize the left half, then finds all the ways to parenthesize the right half, and looks at all possible combinations of the left half with the right half.

The amount of work is to look at each combination of left- and right-half sub problem results is that the product of the number of ways to do the left half and the number of ways to do the right half.

Second case: For each possible place to split the matrix chain, RECURSIVE-MATRIX-CHAIN finds the best way to parenthesize the left half, then finds the best way to parenthesize the right half, and combines just those two results.

• The amount of work to combine the left- and right-half sub problem results is O(1).

Running times of both cases:

• The run time of enumerating is: n P(n).
• The run time of RECURSIVE-MATRIX-CHAIN, it would also have to run on all of the internal nodes of the sub problem tree.

From this, we can say running RECURSIVE-MATRIX-CHAIN is more efficient way.

16.2.

The maximum weight is an integer.

Let S be the optimal solution for W and i be the highest numbered item in S, the items are 1,...,n

S' = S - {i} is an optimal solution for W-w_i and items 1,...i-1

The value of the solution in S is the value v_i of item i and the value of the solution S'.

Let c[i,w] be the value of the solution for items 1,...i and maximum weight w.

The value of the solution for i items either includes item i, in which it is v_i plus a sub problem solution for i-1 items and the weight including w_ior doesn't include the item i.

Algorithm is:

Inputs: W, n, v = <v₁, v₂,...., v_n> and w = <w₁, w₂,...., w_n>

DYNAMIC-0-1-KNAPSACK (v,w,n,W)

for w <- 0 to W do

c[0,w] <- 0

end for

for i <- 1 to n do

c[i,0] <- 0

for w <- 1 to W do

if wi <= w then

if vi + c[i-1, w-wi] > c[i-1, w] then

c[i, w] <- vi + c[i-1, w-wi]

else

c[i, w] <- c[i-1, w]

end if

else

c[i, w] <- c[i-1, w]

end if

end for

end for

return c[n, W]

Answer 2

15.3-1: Running the RECURSIVE-MATRIX-CHAIN algorithm is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem compared to enumerating all the ways of parenthesizing the product and computing the number of multiplications for each.

The reason is that the RECURSIVE-MATRIX-CHAIN algorithm utilizes dynamic programming to avoid redundant calculations. It breaks down the problem into smaller subproblems and stores the results of these subproblems in a table, which can be accessed later. By utilizing the results of the subproblems, the algorithm avoids recalculating the same subproblems multiple times, significantly reducing the number of computations.

On the other hand, enumerating all the ways of parenthesizing the product and computing the number of multiplications for each would involve calculating the number of multiplications for every possible parenthesization, which results in an exponential number of computations. This approach becomes increasingly inefficient as the number of matrices increases.

Therefore, the RECURSIVE-MATRIX-CHAIN algorithm, with its dynamic programming approach, is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem.

16.2-2: Here's a dynamic programming solution to the 0-1 knapsack problem that runs in O(nW) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack:

javaCopy codepublic class Knapsack {    public static int knapsack(int[] weights, int[] values, int n, int W) {        int[][] dp = new int[n + 1][W + 1];        for (int i = 1; i <= n; i++) {            for (int w = 1; w <= W; w++) {                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }        return dp[n][W];
    }    public static void main(String[] args) {        int[] weights = {2, 3, 4, 5};        int[] values = {3, 4, 5, 6};        int n = weights.length;        int W = 8;        int maxProfit = knapsack(weights, values, n, W);
        System.out.println("Maximum Profit: " + maxProfit);
    }
}

In this solution, we use a 2D array dp to store the maximum possible profit for each subproblem. We iterate through each item and weight combination, and for each item, we check if it can be included in the knapsack based on its weight. If it can be included, we calculate the maximum profit by either including or excluding the item, and take the maximum of the two choices.

By using dynamic programming and storing the results of subproblems in the dp array, we avoid redundant calculations and achieve a time complexity of O(nW), where n is the number of items and W is the maximum weight of the knapsack.