作者suhorng ( )
站內Prob_Solve
標題Re: [問題] 20 個數字分三堆使得 最大的堆 為最小
時間Sat Jan 7 21:18:20 2012
※ 引述《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
1F：→ tkcn:不過 3^20 也不太大，搭配 B&B 應該會比這還快 01/07 23:49
2F：→ suhorng:對呀 01/08 00:14
3F：推 singlovesong:3^20 是什麼解法..@@ 01/08 09:10
4F：→ x000032001:3(堆)^(20個數字)? 01/08 14:48
5F：→ tkcn:是的，其實就是將 20 個數字分成三堆的所有方法之數量 01/08 17:35
6F：推 dreamoon:若用這篇的這個方法,可以限制u<=v<=2000,大概快個8倍 01/10 08:56
7F：→ dreamoon:若枚舉的話應該是3^17 01/10 08:57
8F：推 dreamoon:對不起我錯了沒舉不是3^17...不要理我好了 01/10 10:21
9F：推 flere:樓上不是uva世界排名前5的高手嗎XDD 01/10 12:44
10F：→ flere:暴力法配B&B應該會過吧..?! 01/10 12:45
11F：推 singlovesong:3^20 不是36億左右嗎... 怎麼可能夠0.0 01/13 19:31
12F：→ suhorng:那前提是要跑滿吧 ? 01/13 21:44
13F：→ bleed1979:這是那一題啊，好久沒 judge 了，想 send send 看。 01/13 21:55