作者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