Skip to main content
move the attempt to answer
Source Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?


Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$ where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.

Is this a correct dynamic programming algorithm?

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?


Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$ where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.

Is this a correct dynamic programming algorithm?

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?

problem edited
Source Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?


Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$ where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.

Is this a correct? Are there any efficient dynamic programming algorithmsalgorithm?

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?


Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$ where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.

Is this correct? Are there any efficient dynamic programming algorithms?

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?


Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$ where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.

Is this a correct dynamic programming algorithm?

Source Link
hengxin
  • 9.6k
  • 3
  • 37
  • 74

Optimal substructure and dynamic programming for a variant of the rod cutting problem

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?


Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$ where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.

Is this correct? Are there any efficient dynamic programming algorithms?