r**a
发帖数: 536 | 1 以前在什么地方见过，忘记咋做了。哪位兄台给个hint？
已知将一段长为(m+n)的小木棍切成长分别为m和n的两段需要的力量为(m+n)，现需要
将一段长为45的小木棍切成长度分别为1到9的9段，怎么切最省力？ | c******0
发帖数: 59 | 2 DP
每次找两个数相加和最小的那个.
举例:
15分1,2,3,4,5
倒着数:
1: 1+2
2: 3+3
3: 4+5
4: 6+9 | r**a
发帖数: 536 | 3 Thanks for the reply. Oops, suddenly find that i misunderstood the question.
I thought the lengths of 9 pieces are undetermined and can be any number
from 1 to 9. If the lengths of the 9 pieces are 1, 2, ..., 9, then following
your idea it is easy to solve.
May I ask whether you have any idea if the lengths of the 9 pieces are
unknown?
【在 c******0 的大作中提到】
: DP
: 每次找两个数相加和最小的那个.
: 举例:
: 15分1,2,3,4,5
: 倒着数:
: 1: 1+2
: 2: 3+3
: 3: 4+5
: 4: 6+9
| c******0
发帖数: 59 | 4 If the lengths are unknown then:
1. assuming iteration allowed:
bi-section method. Half it to two numbers that can lead to the average num.
The sum you get from each run, is one of the (or two) numbers you obtained
from last cut. So the more you are left off with from each cut, the worse
the algo is.
e.g. 10 into 5 numbers
10 = 4 + 6 (cost 10) = 2 + 2 + 2 + 4 (cost 10) = 2 + 2 + 2 + 2 + 2 (cost 4)
in fact this algo leaves with a cost of target*num iteration + last split (2
*avg)
2. assuming no iteration allowed:
pretty much find sum(n_1...n_9) > target
since distinct numbers are required, and you need them to be close (to have
a smaller number for next cut)
question.
following
【在 r**a 的大作中提到】
: Thanks for the reply. Oops, suddenly find that i misunderstood the question.
: I thought the lengths of 9 pieces are undetermined and can be any number
: from 1 to 9. If the lengths of the 9 pieces are 1, 2, ..., 9, then following
: your idea it is easy to solve.
: May I ask whether you have any idea if the lengths of the 9 pieces are
: unknown?
| r**a
发帖数: 536 | 5 Many thanks for the reply. I really appreciate it. I am wondering if there
is a reference regarding this.
.
obtained
4)
(2
【在 c******0 的大作中提到】
: If the lengths are unknown then:
: 1. assuming iteration allowed:
: bi-section method. Half it to two numbers that can lead to the average num.
: The sum you get from each run, is one of the (or two) numbers you obtained
: from last cut. So the more you are left off with from each cut, the worse
: the algo is.
: e.g. 10 into 5 numbers
: 10 = 4 + 6 (cost 10) = 2 + 2 + 2 + 4 (cost 10) = 2 + 2 + 2 + 2 + 2 (cost 4)
: in fact this algo leaves with a cost of target*num iteration + last split (2
: *avg)
| c******0
发帖数: 59 | 6 No idea..
【在 r**a 的大作中提到】
: Many thanks for the reply. I really appreciate it. I am wondering if there
: is a reference regarding this.
:
: .
: obtained
: 4)
: (2
|
|
