题目来源:https://leetcode.com/problems/tallest-billboard/description/
标记难度:Hard
提交次数:1/2
代码效率:
- 动态规划:136ms
- 中间相遇:184ms
题意
给定<=20根棍子,要求从中拿出一些,分成两组,使得每组的棍子长度之和相等。保证所有棍子的长度之和最大是5000。
分析
在比赛的时候我能想到的最好的解法是这样的:
- 枚举第一组都有哪些棍子(
2^20
) - 对于剩下的棍子,用动态规划的方法判断能否组成第一组已有的长度(
5000*20
)
显然这个算法是会超时的。但是也许它已经接近正解了。
解法1:-1,0,1背包
把这个问题看成是扩展版的01背包问题:对于每根棍子,我们可以把它加入背包中,不加入背包中,还可以把它从背包中减去。
令f[i][j]
表示用前i
根棍子能否组成和为j
的长度(j
有可能是负的)。则f[i+1][j] = f[i][j] || f[i][j-rods[i+1]] || f[i][j+rods[i+1]]
。为了找到可能的最大长度,用辅助数组g[i][j]
记录f[i][j]
为真时,最大可能的正长度之和。算法的复杂度为O(10000*N)
。[1]
解法2:中间相遇法
把rods
数组分成大致相等的两半,然后对每一半都枚举每根棍子是+,-还是0。然后对于左边的一半得到的和,在右边寻找这个和的负值是否存在。最后取最大值。算法复杂度为O(3^(N/2))
。
这个算法也需要记录最大可能的正长度之和。
代码
解法1:扩展01背包
1 | class Solution { |
解法2:中间相遇法
1 | class Solution { |