tying ropes in minimum cost
john suggested a game.you have n ropes of varying length and you have to tie them together.The cost of tying two ropes is sum of length of two ropes.suggest a way for tying ropes in minimum cost.
Note:suppose there are three ropes x,y,z such that x < y < z then if you tie y and z cost is (y+z) and tie x to it is x+2*(y+z).
Note:suppose there are three ropes x,y,z such that x < y < z then if you tie y and z cost is (y+z) and tie x to it is x+2*(y+z).
if you have three ropes of length x<y<z.then if you tie in order x,y,z then cost is z+2*(x+y)and for order x,z,y cost is y+2*(x+z),so z+2*(x+y)<y+2*(x+z) this means that if we tie ropes in increasing order then cost is least.
ReplyDeleteSo use mean heap and extract ropes one by one to tie.