Re: [問題] 20 個數字分三堆使得 最大的堆 為最小

[suhorng ( )]

※ 引述《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
→ tkcn:不過 3^20 也不太大，搭配 B&B 應該會比這還快
→ suhorng:對呀
推 singlovesong:3^20 是什麼解法..@@
→ x000032001:3(堆)^(20個數字)?
→ tkcn:是的，其實就是將 20 個數字分成三堆的所有方法之數量
推 dreamoon:若用這篇的這個方法,可以限制u<=v<=2000,大概快個8倍
→ dreamoon:若枚舉的話應該是3^17
推 dreamoon:對不起我錯了沒舉不是3^17...不要理我好了
推 flere:樓上不是uva世界排名前5的高手嗎XDD
→ flere:暴力法配B&B應該會過吧..?!
推 singlovesong:3^20 不是36億左右嗎... 怎麼可能夠0.0
→ suhorng:那前提是要跑滿吧 ?
→ bleed1979:這是那一題啊，好久沒 judge 了，想 send send 看。