You are given a rod of Length n feet and a List of pairs tha

You are given a rod of Length n feet and a List of pairs that contain the prices of pieces of various sizes. For instance, [[1, 1], [2, 3]] means that a 1-foot rod costs $1 and a 2-foot rod costs $3. Complete the rod_cutter function found below. The function should compute the maximum value that can be obtained by cutting up the rod and selling the pieces. For example, if Length of the rod is 4 feet Long and the values are [[1, 1], [2, 3]] the maximum value is 6, obtained by cutting the rod into two pieces of Length 2, each worth $3.

Solution

#function to check if we can use the value
# returns true if value is less than or equal to what is remaining to be compensated
def valid(value, remaining):
    return remaining>=value

#main algorithm. Goes recursively and checks after each call if we need to compensated
#more and calculates the value if we used a particular piece or didn\'t use it.
#Then it looks at what gives maximum value out of the 2. Then it uses or ignores as desired.
def use_it_lose_it(values, remaining):

    if remaining==0 or len(values)==0:
        return 0

    elif not valid(values[0][0], remaining):
        return use_it_lose_it(values[1:], remaining)

    else:
        lose = use_it_lose_it(values[1:], remaining)
        use = values[0][1] + use_it_lose_it(values, remaining-values[0][0])
        return max(lose, use)

values = [[1, 1], [2, 3]]
total = 4
print \"Maximum value obtained: \", use_it_lose_it(values, total)