Question

Suppose that in the rod-cutting problem, we also had limit li on the number of pieces of length l that we are allowed to produce for i = 1, 2, .... N. Show that the optimal-substructure property no longer holds.

Answer 1

When there are limits on the number of pieces of each length in the rod-cutting problem, the optimal-substructure property no longer holds.

Step-by-step explanation:

In the original rod-cutting problem, the optimal-substructure property holds, meaning that the solution to a larger problem can be constructed from the solutions to smaller subproblems. However, when we have limits on the number of pieces of each length that we are allowed to produce, the optimal-substructure property no longer holds.

For example, let's say we have a rod of length L and we are only allowed to produce a maximum of two pieces of length L/2. In this case, the optimal solution may involve cutting the rod into two equal pieces of length L/2, even though that may not be the optimal solution for a smaller subproblem.

Therefore, when there are limits on the number of pieces of each length that we can produce, the optimal-substructure property is violated.