Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Rod Cutting

Medium · Dynamic Programming · Asked at Amazon, Microsoft, Google

A rod of length n can be cut into pieces of integer lengths; a piece of length i sells for price[i]. Print the maximum revenue (you may also sell the rod uncut).

Input

First line: n. Second line: price[1] … price[n].

Output

The maximum revenue.

Constraints

best[L] = max over the first piece length i ≤ L of price[i] + best[L − i]. It is an unbounded knapsack on lengths.

Example 1

Input

8
1 5 8 9 10 17 17 20

Output

22

Example 2

Input

8
3 5 8 9 10 17 17 20

Output

24

Hints

  1. Decide the length i of the first piece; the rest of the rod (L − i) should then be cut optimally.
  2. best[L] = max over i from 1 to L of price[i] + best[L − i], with best[0] = 0.

Approach

Compute best for lengths 1..n in increasing order. For each length try every first-piece length; the remaining part's optimum is already known. This is the unbounded knapsack where the item weights are the lengths 1..n.

Complexity: O(n²) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> p(n + 1), best(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int L = 1; L <= n; L++)
        for (int i = 1; i <= L; i++) best[L] = max(best[L], p[i] + best[L - i]);
    cout << best[n] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
p = [0] + data[1 : 1 + n]
best = [0] * (n + 1)
for L in range(1, n + 1):
    best[L] = max(p[i] + best[L - i] for i in range(1, L + 1))
print(best[n])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] p = new long[n + 1], best = new long[n + 1];
        for (int i = 1; i <= n; i++) p[i] = sc.nextLong();
        for (int L = 1; L <= n; L++)
            for (int i = 1; i <= L; i++) best[L] = Math.max(best[L], p[i] + best[L - i]);
        System.out.println(best[n]);
    }
}

Solve Rod Cutting online · All practice problems