j*******a
发帖数: 45 | 1 【 以下文字转载自 CS 讨论区 】
发信人: jinghanna (benben), 信区: CS
标 题: 请教一道算法题
发信站: BBS 未名空间站 (Fri Jul 20 00:06:59 2007), 站内
有一根绳子上面打了M个结，这M个结把绳子分成了M+1段，记为L1,L2,...,LM+1。现在
需要把绳子分成N段（N
段后的绳子的长度(L1',L2',...,LN')尽可能的相等。如果把这一个要求量化的话，就
是使分段后的绳子长度的平房和最小，即 minimize L1'^2+L2'^2+...+LN'^2。 | N*****N
发帖数: 1605 | 2 这个没人解阿?
M个结是平均的么?
看似是C(N-1,M)总分法,NP问题.需要近似求解?
N
【在 j*******a 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: jinghanna (benben), 信区: CS
: 标 题: 请教一道算法题
: 发信站: BBS 未名空间站 (Fri Jul 20 00:06:59 2007), 站内
: 有一根绳子上面打了M个结，这M个结把绳子分成了M+1段，记为L1,L2,...,LM+1。现在
: 需要把绳子分成N段（N: 段后的绳子的长度(L1',L2',...,LN')尽可能的相等。如果把这一个要求量化的话，就
: 是使分段后的绳子长度的平房和最小，即 minimize L1'^2+L2'^2+...+LN'^2。
| N*****N
发帖数: 1605 | 3 想起来了，Dynamic Programming，典型的，算法懒得写了，画个表就出来了，跟那个矩
阵相乘找乘法数最小的组合的基本一样，呵呵
【 以下文字转载自 CS 讨论区 】
发信人: jinghanna (benben), 信区: CS
标 题: 请教一道算法题
发信站: BBS 未名空间站 (Fri Jul 20 00:06:59 2007), 站内
有一根绳子上面打了M个结，这M个结把绳子分成了M+1段，记为L1,L2,...,LM+1。现在
需要把绳子分成N段（N
段后的绳子的长度(L1',L2',...,LN')尽可能的相等。如果把这一个要求量化的话，就
是使分段后的绳子长度的平房和最小，即 minimize L1'^2+L2'^2+...+LN'^2。
【在 j*******a 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: jinghanna (benben), 信区: CS
: 标 题: 请教一道算法题
: 发信站: BBS 未名空间站 (Fri Jul 20 00:06:59 2007), 站内
: 有一根绳子上面打了M个结，这M个结把绳子分成了M+1段，记为L1,L2,...,LM+1。现在
: 需要把绳子分成N段（N: 段后的绳子的长度(L1',L2',...,LN')尽可能的相等。如果把这一个要求量化的话，就
: 是使分段后的绳子长度的平房和最小，即 minimize L1'^2+L2'^2+...+LN'^2。
|
|
