Limited access

Suppose we run a candy factory. Every day, we produce long strands of licorice, which need to be cut into manageable lengths before they can be sold to our customers. Each length of licorice sells for a different price, based on certain economic factors. Since we're enterprising businessmen, we want to maximize the total amount of profit we can obtain from a given length of licorice.

Supposing our customers are only interested in purchasing licorice strands that can be measured in whole inches, into what sizes should we cut our rods in order to obtain the maximum profit?

This is more formally known as the rod-cutting problem, where we replace "licorice" by "rods". This problem can be formally defined as follows:

Input: A set of prices for lengths of rod, $p_1,...,p_n$, each $p_i$ is the price of a rod of length $i$.
Output: $a_1, ..., a_n$, where each $a_i$ is the maximum profit which can be obtained for a rod of length $i$.

This problem can be solved using dynamic programming. As we know, in order to apply dynamic programming, we must first show that optimal substructure holds. This is typically done using a recurrence relation.

Let $a_i$ be the maximum profit that can be obtained for a rod of length $i$. For convenience, we also define the price of an "empty rod" to be $p_0 = 0$.

Which of the following recurrence relations are correct for this problem?

Select ALL that apply.

A

$a_i = a_{i-1}+p_i$
$a_1= p_1$

B

$a_i = \displaystyle\max_{i=j+k} (a_j + a_k)$
$a_1 = p_1$

C

$a_i = \displaystyle\max_{1 \leq j \leq i} ( a_j + p_j)$
$a_1 = p_1$

D

$a_i = \displaystyle\max_{0 \leq j \leq i-1} (a_j + a_{i-j})$
$a_1=p_1$
$a_0 = 0$

Select an assignment template