I'm not 100% certain exactly what your requirements are, so I may be missing something.
My understanding is you start with one board, and you need to cut it into n pieces of different length. The cost of cutting any piece depends on the size of the board (I assume longer boards are more expensive?).
Do I have that right?
So let's look at a simple example.
Let's say it cost:
10ft board - $10
9ft board - $9
............
I think you can see the pattern I'm going for.
Let's say:
L1=1ft
L2=6ft
L3=3ft
So we have:
|-|------|---| (L1, L2, L3)
It's easy to see the cheapest way to cut this is at the 7ft mark, and then the 1ft mark. (I'm counting the marks on the original 10ft board).
1 10ft cut - $10
+ 1 7ft cut - $ 7
------------------
$17
But if you're allowed to move the pieces around you can do it cheaper.
look at this:
|------|-|---| (L2, L1, L3)
It's easy to see the cheapest way to cut this is at the 6ft mark, and then the 7ft mark.
1 10ft cut - $10
+ 1 4ft cut - $ 4
------------------
$14
Did I miss something, I don't think your algorithm caught this case?
I'm afraid I just raised you complexity a bunch, but it's not as bad as it may seem at first. There are lot's of duplicates you can get rid of.
For example:
|------|-|---| (L2, L1, L3)
Is the same as:
|---|-|------| (L3, L1, L2)
It's just the same board flipped.
It's also the same as:
|-|---|------| (L1, L3, L2)
It's just that this time you also flipped the second board
before cutting it.
I'm I making sense?
|
