作者chrisdar (克里斯)
看板Programming
标题[问题] 数列分段的问题
时间Fri May 1 16:47:14 2009
※ [本文转录自 C_and_CPP 看板]
作者: chrisdar (克里斯) 看板: C_and_CPP
标题: [问题] 数列分段的问题
时间: Fri May 1 16:46:08 2009
现在有一数列与分段清况如下：
23,6,4,5,3,3,3,4,5,2,2,4,5,5,6,23,3,3,7,6,6,4,3,5,5,7,4,5,3,4,6,23,10
| 47/50 | 22/45 | 37/40 | 34/45 | 67/50 |
何谓 47/50 ：该段数列总和47希望调整到50以内
有些原则需要遵守：
1. 不要更动数列的顺序
2. 满足各段数列总和均小於要求
举例：下面即是一个可行解
输入| 47/50 | 22/45 | 37/40 | 34/45 | 67/50 |
23,6,4,5,3,3,3,4,5,2,2,4,5,5,6,23,3,3,7,6,6,4,3,5,5,7,4,5,3,4,6,23,10
输出| 47/50 | 33/45 | 36/40 | 45/45 | 46/50 |
定义成本：输出入之间各段的数列个数差的总和
以例子来说 cost=0(第一段)+2(第二段)+0(第三段)+2(第四段)+4(第五段)=8
我们希望成本越小越好，这题目不知道该怎麽做？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.195.88.23
※ chrisdar:转录至看板 Prob_Solve 05/01 16:46
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.195.88.23
1F：推 bobju:怎麽这麽巧?最近出现好多类似的题目: 乌龟塔 59.104.191.26 05/02 08:51
2F：→ bobju:,锯木,etc.. 59.104.191.26 05/02 08:51
3F：→ bobju:对了,还有ajax版的两点间最短路径的程式马. 59.104.191.26 05/02 08:52
4F：→ bobju:这些题目难度比较高,即使修过演算法也未必提 59.104.191.26 05/02 08:53
5F：→ bobju:得出答案来. 59.104.191.26 05/02 08:53
6F：→ chrisdar:谢谢以上的推文 123.195.88.23 05/06 10:40