CODEWITHSUNDEEP
pythonalgorithmdynamic-programming
user1530318
user1530318

Reputation: 27757

Python Rod Cutting Algorithm - Variant

I was asked this as a brain teaser in one of my classes but was unable to figure it out (Wasn't a homework question, just a teaser one of the TA's gave us to think about).

You are given a rod with a list of n points to cut at, for example [1,5,11], and the total length of the rod, for example 20. You are also told that the expense of cutting a rod is equivalent to that of the length of the rod. We want to find the minimum cost of cutting the rod at all the given cuts and the sequence of those cuts that would lead to the optimal cost.

For example, to cut a rod of length 20 at position 5, it would cost you $20 and you would end up with 2 logs, one with length 5 and one with length 15.

Or in another example, if you cut a rod of length 25 at positions 5 and then at position 10, it would cost you $25 to cut it at position 5, leaving you with a length 5 rod and a length 20 rod, and then cost you another $20 to cut it at position 10, giving you the total cost of cutting at the two positions at $45. However if you cut the rod at position 10 and then position 5, it would cost you $25 + $10 = $35.

In the end, we want to return the minimum cost of cutting the rod at all the given cuts and the sequence of those cuts that would lead to the optimal cost.

I attempted to come up with a recursive solution for this problem, but kept coming up empty-handed. Thoughts? Any help is appreciated. Thanks!

Upvotes: 2

Views: 2301

Answers (2)

Bug Hunter 219
Bug Hunter 219

Reputation: 344

In order to solve this problem you have to use a Dynamic Programming Approach. It's an O(n^3) based solution .(Please comment if somebody has better solution) . Let us have an array a[n+1][n+1] where n= length of the rod. a[i][j] will store the minimum cost of cutting the rod from position i to position j. We are given a cut array which has all the positions where to cut the rod. For every i-j rod we consider cutting it all k positions which are been given in the cut array and find out the minimum cost. We fill the array in the diagonal fashion. (Comment if needed more explaination)

#include <iostream>
#include <string.h>
#include <stdio.h>  
#include <limits.h>
using namespace std;
int main(){
   int i,j,gap,k,l,m,n;
   while(scanf("%d%d",&n,&k)!=EOF){

    int a[n+1][n+1];
    int cut[k];
    memset(a,0,sizeof(a));
    for(i=0;i<k;i++)
        cin >> cut[i];
    for(gap=1;gap<=n;gap++){
        for(i=0,j=i+gap;j<=n;j++,i++){
            if(gap==1)
                a[i][j]=0;
            else{
                int min = INT_MAX;
                for(m=0;m<k;m++){
                    if(cut[m]<j and cut[m] >i){
                        int cost=(j-i)+a[i][cut[m]]+a[cut[m]][j];

                        if(cost<min)
                            min=cost;
                    }
                }
                if(min>=INT_MAX)
                a[i][j]=0;
                else
                    a[i][j]=min;
            }
        }
    }
    cout << a[0][n] << endl;
}
return 0;
}

Upvotes: 0

m.brindley
m.brindley

Reputation: 1228

I believe the point of the rod cutting problem is that a greedy algorithm will not always produce the optimal solution - this variant seems to prove the same point.

Consider the L=50 rod to be cut at [13,25,26]. An algorithm selecting the cut closest to the mid-point would tell you to do [25, 13, 26] for a total cost of 50 + 25 + 25 = 100. We can improve on that by doing [26, 13, 25] for a total cost of 50 + 26 + 13 = 89.

Edit:

ie. You would cut an L=50 rod at P=26 resulting in an L=24 (P=26->50) rod that needs no more cuts and an L=26 (P=0->26) rod that needs to be cut at [25,13]. Then you cut the L=26 rod at P=13 resulting in one L=13 (P=0->13) rod needing no more cuts and a second L=13 (P=13->26) rod needing a final cut at P=25. Then you do the final cut resulting in a cost that is the sum of the lengths of the rods which were cut at each stage (50 + 26 + 13).

The alternatives usually proposed are top-down and bottom-up techniques and the efficiency of these usually depend on the logic involved (for the traditional rod cutting problem in which you are trying to maximise sale cost, bottom-up is preferred as it reduces recursive calls).

Upvotes: 1

Related Questions