wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Minimum cost of cutting a Wooden log 
        
(Message started by: hary on Feb 1^st, 2010, 11:35pm)

Title: Minimum cost of cutting a Wooden log
Post by hary on Feb 1^st, 2010, 11:35pm

You are given a wooden log of length n. It has n+1 grooves marked on it from 0 to n. You are given an array containing numbers within the range of 1 to n-1. These elements of the array represents the points on the log at which u need to cut the wooden log. Now the cost of cutting a log is proportional to the length of the original log being cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this log is 9-1=8, so the cost will be 8.
Ques : given the value of 'n' and the Array A containing the points at which u need to make a cut, find the order in which the cuts must be made in order to minimize the total cost of cutting the wooden log.

Title: Re: Minimum cost of cutting a Wooden log
Post by birbal on Feb 2^nd, 2010, 2:35am

Each time you make a cut, try to make it such that it divides the log in two small logs which are as similar in size as possible. I think this strategy will work.

Title: Re: Minimum cost of cutting a Wooden log
Post by Grimbal on Feb 2^nd, 2010, 5:41am

It doesn't always work.

If n=10, A={1,2,3,4,5,6}

If you cut at 5, you need 5+2+3+2=12 for the left part and 5 for the right part. The total cost is 10+12+5=27.

If you cut at 6, you need 6+3+2+3+2=16 for the left part and nothing for the right part. That is 10+16+0 = 26 total.

Title: Re: Minimum cost of cutting a Wooden log
Post by inexorable on Feb 2^nd, 2010, 4:38pm

Dynamic programming is to be used.

[hideb]
vector<vector<int> > cuts(int n, vector<int> A)
{
int min;
int numcuts = A.size();
vector<vector<int> > Cuts(vector<int> V(0,n), n);
vector<vector<int> > Result(vector<int> V(0,n), n);

for(int i=0;i<numcuts;i++)
{
Cuts[A[i][A[i]=0;
Cuts[A[i][A[i+1]=0;
}

for(int cutlen=2;cutlen<numcuts;cutlen++)
for(int i=0;i<(numcuts-cutlen);i++)
{
min=INT_MAX;
for (k = i + 1; k < (i + cutlen); ++k)
{
if(min < (Cuts[A[i][A[k] + Cuts[A[k][A[i+cutlen]))
Result[A[i][A[i+cutlen]=k;
}
Cuts[i][i+len] = min + A[i + len] - A[i];
}

return Result;
}
[/hideb]

Title: Re: Minimum cost of cutting a Wooden log
Post by hary on Feb 2^nd, 2010, 9:57pm

Inexorable, It would be very nice of you if you can explain it with an example trace on a small set of data say 5 elements in the cut array.

i will quote the example for you .
cutarray[ ] = {2, 5, 8, 9, 13} and length of original log = 15
Thanks.

Title: Re: Minimum cost of cutting a Wooden log
Post by inexorable on Feb 3^rd, 2010, 12:59pm

Recursive relation would be

f(0,15)= min(f(0,k)+f(k,15))+15(current length).

k varies from cutarray[0] to cutarray[4]

I hope this explains better. In previous post i used dynamic programming to get the solution in Optimal time.

Title: Re: Minimum cost of cutting a Wooden log
Post by hary on Feb 4^th, 2010, 10:54pm

on 02/03/10 at 12:59:32, inexorable wrote:

Recursive relation would be

f(0,15)= min(f(0,k)+f(k,15))+15(current length).

So a few things, while taking a trace of DP solution, i see some oddities due to which i get confused,
Even in the recursive solution i see a "+" instead of a ","
In total i am still not able to get the soltuion.
I tried tracing on a smaller example.
cutarray = {2,3,5} and length = 7. I think i am a nut when it comes to understand the DP problems. Please help

Title: Re: Minimum cost of cutting a Wooden log
Post by hemanshu on Feb 7^th, 2010, 6:50am

i think instead of second "+" dere should be "," ...

Title: Re: Minimum cost of cutting a Wooden log
Post by Grimbal on Feb 8^th, 2010, 1:09am

To me
f(0,15) = min(f(0,k)+f(k,15))+15
is correct.

In general,
f(a,b) = min(f(a,k)+f(k,b)) + (b-a)
where a<k<b and k is in cutarray, with the exception
f(a,b) = 0
if there is no such k.