Question

There is a stick of length N. You want to cut and sell the stick. Each cut has a different price depending on its length. Design an algorithm to find the optimal way to cut the stick into two pieces and the sum of prices is maximized. A list of pairs (length, price) is given. For instance, {(1,1), (2,5), (3,8), (4,9)} and N = 4. The optimal solution in this case is cutting into two pieces of length 2 each and its price sum is 5 + 5 10.

Your algorithm’s time complexity should be no larger than O(N²).

The algorithm should be designed to cut the stick into two pieces only no more no less. Edge cases are not necessary just general algorithm for optimal way to cut the stick will be sufficient.

Answer 1

Answer:

We are creating an algorithm using Bottom Up Solution:

Algorithm:

ExtendedBottomUpStick(p, n)
        s: array(0..n)    //optimal value for sticks of length 0 to n
        a: array(0..n)    //optimal first cut for stick of length 0 to n
        s(0) := 0
        for j in 1 .. n loop
            q := MinInt
            for i in 1 .. j loop  //Find the max cut position for length j
                if q < p(i) + s(j-i) then
                    q := p(i) + s(j-i)
                    a(j) := i    //Remember the value of best so far value of i
                end if
            end loop
            s(j) := q
        end loop
        return s and a

    PrintCutStickSolution(p, n)
        (s, a) := ExtendedBottomUpStick(p, n)
        while n > 0 loop
            print a(n)
            n := n - a(n)
        end loop

Here, s[] -> stick array

a[] -> Optimal first cut for stick of length from 0 to N

This bottom up solution require O(n²) time.

Hope I answered the question.

If you have any doubts, or queries, feel free to ask

I'll respond to you as soon as I can.

Have a nice day