LeetCode: Tallest Billboard

Posted on August 5, 2019July 26, 2020 by braindenny

Tallest Billboard

Similar Problems:

You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.

You have a collection of rods which can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.

Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.

Example 1:

Input: [1,2,3,6]
Output: 6
Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.

Example 2:

Input: [1,2,3,4,5,6]
Output: 10
Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.

Example 3:

Input: [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.

Note:

0 <= rods.length <= 20
1 <= rods[i] <= 1000
The sum of rods is at most 5000.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/tallest-billboard
// Basic Ideas: knapsack problem
//
// Design algorithm:
//
//  Observation: For each cell, there are 3 decision choices
//  Observation: sum of one side can't be bigger than 2500
//
//  Q: How to manage [-2500, 2500]?
//  A: Add 2500 to map it
//
//  Q: How to confirm both v and -v are reachable?
//  A: When value hits 0, and the sum of one side is positive
//
//  Q: How to get the maximum target?
//
//  dp[i][s] bool
//       dp[i-1][s-rods[i]] || dp[i-1][s+rods[i]] || dp[i-1][s]
//  max[i][s] int
//   target is max[n][2500]
//     
// Complexity: Time O(n*s), Space O(n*s)
func getMax(x int, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}
func tallestBillboard(rods []int) int {
    dp := make([][]bool, len(rods)+1)
    max := make([][]int, len(rods)+1)
    for i, _ := range dp {
        dp[i] = make([]bool, 5001)
        max[i] = make([]int, 5001)
    }
    dp[0][2500] = true
    for i:=1; i<=len(rods); i++ {
        for j:=0; j<5001; j++ {
            // drop it
            if dp[i-1][j] {
                dp[i][j] = true
                if max[i-1][j] > max[i][j] {
                    max[i][j] = max[i-1][j]
                }
            }
            // put it to side1
            if j-rods[i-1]>=0 && dp[i-1][j-rods[i-1]] {
                dp[i][j] = true
                max[i][j] = getMax(max[i][j], max[i-1][j-rods[i-1]]+rods[i-1])
            }
            // put it to side2
            if j+rods[i-1]<5001 && dp[i-1][j+rods[i-1]] {
                dp[i][j] = true
                max[i][j] = getMax(max[i][j], max[i-1][j+rods[i-1]])
            }
        }
    }
    return max[len(rods)][2500]
}

Post Views: 0