0
$\begingroup$

I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill.

Given a board of length $n$, and an increasing monotonic "price" function $p:\mathbb{N}\rightarrow\mathbb{R}^+ $, an acceptable partition (Notated by $X=\{x_1,x_2,\ldots x_m\}$) of the board to $m\leq n$ pieces is defined by: $$ x_1, x_2, \ldots x_m \in \mathbb{N}^+ $$ $$ \sum^{m}_{i=1}x_i=n $$ the profit of an acceptable partition is defined to be the sum:$$\sum^{m}_{i=1}p(x_i)$$

The problem asks to describe an efficient algorithm to find an acceptable partition which produces the maxiaml profit, out of all acceptable cuts.

I've tried to apply the solution to the "Woodcutter's problem" to this situation, yet the "Woodcutter's Problem" doesnt apply when a price/profit function is introduced.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

This problem is known as the "rod cutting problem". See, e.g., here.

Let $OPT[i]$ denote the maximum profit that can be attained by partitioning a board of length $i$ (according to $p$).

Then $OPT[0] = 0$ since the only acceptable partition has $m=0$. For $i = 1, \dots, n$: $$ OPT[i] = \max_{j=1, \dots, i} \left( p(j) + OPT[i-j] \right). $$

The optimal profit is then in $OPT[n]$. The partition itself can be reconstructed by retracing the dynamic programming choices that led to the value in $OPT[n]$.

$\endgroup$
3
  • $\begingroup$ Just the explanation I was looking for, thank you for describing this so intuitively. $\endgroup$
    – Aishgadol
    Nov 14, 2022 at 17:52
  • $\begingroup$ If I were to prove that this algorithm is optimal, what approach would you recommend? $\endgroup$
    – Aishgadol
    Nov 14, 2022 at 17:54
  • $\begingroup$ @Aishgadol. Interesting question... I don't know of a lower bound argument. Let me know if you find one... $\endgroup$
    – Steven
    Nov 14, 2022 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.