Author |
Topic: Minimum cost of cutting a Wooden log (Read 1501 times) |
|
hary
Junior Member
Posts: 107
|
 |
Minimum cost of cutting a Wooden log
« on: Feb 1st, 2010, 11:35pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Feb 1st, 2010, 11:36pm by hary » |
 IP Logged |
|
|
|
birbal
Full Member
Gender: 
Posts: 250
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #1 on: Feb 2nd, 2010, 2:35am » |
Quote Modify
|
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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #2 on: Feb 2nd, 2010, 5:41am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #3 on: Feb 2nd, 2010, 4:38pm » |
Quote Modify
|
Dynamic programming is to be used.
| hidden: |
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;
}
|
|
|
IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #4 on: Feb 2nd, 2010, 9:57pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #5 on: Feb 3rd, 2010, 12:59pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #6 on: Feb 4th, 2010, 10:54pm » |
Quote Modify
|
on Feb 3rd, 2010, 12:59pm, 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
|
| « Last Edit: Feb 4th, 2010, 10:55pm by hary » |
IP Logged |
|
|
|
hemanshu
Newbie
Gender:
Posts: 14
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #7 on: Feb 7th, 2010, 6:50am » |
Quote Modify
|
i think instead of second "+" dere should be "," ...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Minimum cost of cutting a Wooden log
« Reply #8 on: Feb 8th, 2010, 1:09am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print