Re: [問題] 20 個數字分三堆使得 最大的堆 為最小
看板Prob_Solve (計算數學 Problem Solving)作者suhorng ( )時間13年前 (2012/01/07 21:18)推噓5(5推 0噓 8→)留言13則, 7人參與討論串2/2 (看更多)
※ 引述《singlovesong (~"~)》之銘言：
: 如題
: input 20 個數字 1 <= 每個數字 <=200
: 要把這些數字分三堆使得最大的那堆的和為最小
: 請問這最小的和 為多少？
: ex:
: N=6
: 1 2 3 4 5 6
: 1: 1 6
: 2: 2 5
: 3: 3 4
: ans: 7
: 每堆的數量不限
以下這個方法不是很快：
令 avail[i][u][v] 代表使用前 i (w[1], w[2], ..., w[n]) 個數字
使得第一堆的和為 u、第二堆的和為 v 是否可以做到 (true / false)
之所以只有 [u][v] 是因為三堆的數字和為定值: w[1]+w[2]+...+w[i]
那麼可以有 avail[1][w[1]][0] = true, avail[1][0][w[1]] = true,
avail[1][0][0] = true, avail[1][else][else] = false.
對於第 i 個數字可以選擇放入任一堆:
avail[i][u][v] = avail[i-1][u][v]
or avail[i-1][u-w[i]][v]
or avail[i-1][u][v-w[i]]
最後再掃過陣列, 取 min{ max{u, v, Σw[i] - u - v} } for all u, v
20 個數字每個介在 1 ~ 200 之間, 所以和不超過 4000
20*4000*4000 大概還在可接受範圍內...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.33.1
→
01/07 23:49, , 1F
01/07 23:49, 1F
→
01/08 00:14, , 2F
01/08 00:14, 2F
推
01/08 09:10, , 3F
01/08 09:10, 3F
→
01/08 14:48, , 4F
01/08 14:48, 4F
→
01/08 17:35, , 5F
01/08 17:35, 5F
推
01/10 08:56, , 6F
01/10 08:56, 6F
→
01/10 08:57, , 7F
01/10 08:57, 7F
推
01/10 10:21, , 8F
01/10 10:21, 8F
推
01/10 12:44, , 9F
01/10 12:44, 9F
→
01/10 12:45, , 10F
01/10 12:45, 10F
推
01/13 19:31, , 11F
01/13 19:31, 11F
→
01/13 21:44, , 12F
01/13 21:44, 12F
→
01/13 21:55, , 13F
01/13 21:55, 13F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
