LeetCode 956: tallest billboard

发表于 | | 阅读次数:
字数统计: 394 | 阅读时长 ≈ 1

题目链接

https://leetcode.com/problems/tallest-billboard/

题意

给至多20个数字，数字之和<=5000，在其中找到两个不相交的子集保证两子集分别的和相等，同时使得这个和值尽可能大。

题目类型

动态规划

题目分析

定义动态规划数组f[i][j]表示前i个数字中求和为j时所取得的最大和值，将问题转换为一个背包问题。背包的转移分为三种:把该数作为集合1的值，集合2的值和不加入该数。由此得到三个转移方程:

  • f[i+1][j+rod[i]] = max(f[i+1][j+rods[i]], f[i][j]+rods[i])
  • f[i+1][j-rods[i]] = max(f[i+1][j-rods[i]], f[i][j])
  • f[i+1][j] = max(f[i+1][j],f[i][j])

其中只有在把数字放进集合1的时候才统计其对最大和值的影响；同时为了防止数组和值为负值的时候越界给0加上了5000的偏移量。

时间复杂度

$O(20*10000)$

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int f[22][10020];
    int tallestBillboard(vector<int>& rods) {
        memset(f, -1, sizeof(f));
        f[0][5000] = 0;
        int n = rods.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 10000; j++) {
                if (f[i][j] != -1) {
                    if (j + rods[i] <= 10000)
                        f[i + 1][j + rods[i]] = max(f[i + 1][j + rods[i]], f[i][j] + rods[i]);
                    if (j - rods[i] >= 0)
                        f[i + 1][j - rods[i]] = max(f[i + 1][j - rods[i]], f[i][j]);
                    f[i + 1][j] = max(f[i + 1][j], f[i][j]);
                }
            }
        }
        return f[n][5000] == -1 ? 0 : f[n][5000];
    }
};
0%