| 19 | """ |
| 20 | |
| 21 | def CutRod(n): |
| 22 | if(n == 1): |
| 23 | #Cannot cut rod any further |
| 24 | return prices[1] |
| 25 | |
| 26 | noCut = prices[n] #The price you get when you don't cut the rod |
| 27 | yesCut = [-1 for x in range(n)] #The prices for the different cutting options |
| 28 | |
| 29 | for i in range(1,n): |
| 30 | if(solutions[i] == -1): |
| 31 | #We haven't calulated solution for length i yet. |
| 32 | #We know we sell the part of length i so we get prices[i]. |
| 33 | #We just need to know how to sell rod of length n-i |
| 34 | yesCut[i] = prices[i] + CutRod(n-i) |
| 35 | else: |
| 36 | #We have calculated solution for length i. |
| 37 | #We add the two prices. |
| 38 | yesCut[i] = prices[i] + solutions[n-i] |
| 39 | |
| 40 | #We need to find the highest price in order to sell more efficiently. |
| 41 | #We have to choose between noCut and the prices in yesCut. |
| 42 | m = noCut #Initialize max to noCut |
| 43 | for i in range(n): |
| 44 | if(yesCut[i] > m): |
| 45 | m = yesCut[i] |
| 46 | |
| 47 | solutions[n] = m |
| 48 | return m |
| 49 | |
| 50 | |
| 51 | |