[問題] 數列分段的問題
※ [本文轉錄自 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
推
05/02 08:51, , 1F
05/02 08:51, 1F
→
05/02 08:51, , 2F
05/02 08:51, 2F
→
05/02 08:52, , 3F
05/02 08:52, 3F
→
05/02 08:53, , 4F
05/02 08:53, 4F
→
05/02 08:53, , 5F
05/02 08:53, 5F
→
05/06 10:40, , 6F
05/06 10:40, 6F