Dear All,

I would appreciated if anyone could give me advice about how to solve this problem in C:

1) An integer list of values (lengths of needed pieces) is entered at the input. For example: 4, 7, 6, 3
2) The length of the log is the sum of these values ( 20 in this example )
3) The log has to be cutted into pieces above.
4) The algorithm has to count the lowest possible price of cutting the log. The price of cutting is equal to the length of the log being cutted. It means that if I am cutting the log 20, I have to pay 20. The whole price is sum of all "payments". In the example above, the price is 40.

I was thinking that the list should be saved into an array and after that some kind of sorting algorithm will itterated through the list, but I have not been able to solve this problem so far. Thank you for your hints. 2. Are you suggesting there is a different price to pay if the log is cut in the order 4, 7, 6, 3 compared to say 7, 4, 6, 3 3. He mentions the lowest possible price which makes me think that you'd have to sort the input (here 3, 4, 6, 7) first and then make the i'th cut at the sum of previous i numbers but not so sure as it's bold of me to assume that this will give me the lowest price. In any case, he says the price is supposed to be 40 which if solved along my trail of thought will give you a price of (3 + 7 + 13 = 23) if you cut the 20 units of values at the 3rd, 7th and 13th location, you'd get the the four lengths 3, 4, 6, 7 which is what we need.
1st cut: Sum of first 1 numbers: 3
2nd cut: Sum of first 2 numbers: 7
3rd cut: Sum of first 3 numbers: 13

If it's not to be sorted (which I think is stupid because in the end all you need is the correct length of the pieces with minimum cost), you'd have to make cuts at the 4th, 11th and 17th position for the input 4, 7, 6, 3 which would result to a price of (4 + 11 + 17 = 32) which is not 40 so I don't understand why it would be 40 unless it's a typo. If you understood the reason as to why it's 40, please explain me what's the correct logic. There's a similar problem I solved this way so I'm strongly believing that 40 is not​ the minimum cost. 4. You are misunderstanding the question. The cost of the first cut on a log of length 20 is 20, no matter where you cut it. The dumbest thing to do would be to cut off the smallest piece first. The biggest first might work.

Doing it in order 4, 7, 6, 3, yields:
Code:
```.       20
/    \
4      16          cost: 20
/  \
7    9        cost: 16
/ \
6   3      cost:  9
=========
total: 45```
Doing it in order 7, 6, 4, 3 yields:
Code:
```.       20
/    \
7      13          cost: 20
/  \
6    7        cost: 13
/ \
4   3      cost:  7
=========
total: 40```
Other optimal orders are possible:
Code:
```.        20
/    \
11      9          cost: 20
/  \    / \
7    4  6   3        cost: 20 (11 + 9)
=========
total: 40``` 5. Makes sense, thanks for the explanation. I was thinking of it in a different way as per an old question that I'd come across. 6. Originally Posted by john.c You are misunderstanding the question. The cost of the first cut on a log of length 20 is 20, no matter where you cut it. The dumbest thing to do would be to cut off the smallest piece first. The biggest first might work.

Doing it in order 4, 7, 6, 3, yields:
Code:
```.       20
/    \
4      16          cost: 20
/  \
7    9        cost: 16
/ \
6   3      cost:  9
=========
total: 45```
Doing it in order 7, 6, 4, 3 yields:
Code:
```.       20
/    \
7      13          cost: 20
/  \
6    7        cost: 13
/ \
4   3      cost:  7
=========
total: 40```
Other optimal orders are possible:
Code:
```.        20
/    \
11      9          cost: 20
/  \    / \
7    4  6   3        cost: 20 (11 + 9)
=========
total: 40```
Unfortunately, doing it in order from the highest to the lowest number is not always correct solution. If I have a list of 1 ,2, 3, 8, 9, 9, 21, 31, 45, 71 and 124, I would get a price 868, but the correct answer is 849. It must be a different principle. 7. How exactly do you solve that example and get 849? 8. [QUOTE=john.c;1291304]How exactly do you solve that example and get 849?[/QUOTE

I do not know how to solve it, 849 comes from the correct reference solution (i do not know the code) and my aim is to figure out the correct/ similar algorithm that will give me same results. 9. Hehhee:

log xy = log x + log y
log x/y = log x - log y
log x^y = y * log x

Simple as this...  10. The log here means part of tree. It could be pipe, beam etc.... 11. Originally Posted by arp35 The log here means part of tree. It could be pipe, beam etc....
Nooo... really?!  12. > If I have a list of 1 ,2, 3, 8, 9, 9, 21, 31, 45, 71 and 124, I would get a price 868, but the correct answer is 849. It must be a different principle.
Maybe you're allowed to rearrange the pieces so you can cut more than one log at once. 13. Maybe you're allowed to rearrange the pieces so you can cut more than one log at once.

No matter how many logs is cutting at once. The price is always the length of the log. I am not allowed to cut it into three or more pieces at once. I can cut 100 long log into 50 and 50 or 80 and 20 etc.. but not into f.e. 50, 25 and 25. 14. What are the constraints? How large can the problem be?

I wrote a memoized brute-force program that can solve your 11 element problem very quickly (answer 849) and can solve a 16 element problem in a couple seconds. 15. Originally Posted by john.c What are the constraints? How large can the problem be?

I wrote a memoized brute-force program that can solve your 11 element problem very quickly (answer 849) and can solve a 16 element problem in a couple seconds.
Thank you.

The maximum at the input is 500 000 elements (lengths).  Popular pages Recent additions algorithm, cutting, list, log, price 