This solution uses memoization.

#!/usr/bin/env python
def find_max(list_tuples):
if len(list_tuples) == 0:
return None
maximum = list_tuples[0]
for i in xrange(1, len(list_tuples)):
if maximum[0] < list_tuples[i][0]:
maximum = list_tuples[i]
return maximum
memo = {}
def cutting_rod(prices, ncuts):
if ncuts == 0:
return (0, [])
if ncuts in memo:
return memo[ncuts]
tmp = []
for i in xrange(0, ncuts):
r = cutting_rod(prices, ncuts-i-1)
new_list = list(r[1])
new_list.append(i)
value = prices[i] + r[0]
tmp.append((value, new_list))
result = find_max(tmp)
memo[ncuts] = result
return result
if __name__ == '__main__':
p = [2, 5, 6, 7]
r = cutting_rod(p, len(p))
print "Prices:", p
print "Optimal value:", r[0]
print "Indices:", r[1]
print "Cuts:", [p[x] for x in r[1]]

Output:

Prices: [2, 5, 6, 7]
Optimal value: 10
Indices: [1, 1]
Cuts: [5, 5]

## No comments:

## Post a Comment