Highway Billboard Problem | Python3 program to find maximum revenue by placing billboard on the highway with given constraints . ; Array to store maximum revenue at each miles . ; actual minimum distance between 2 billboards . ; check if all billboards are already placed . ; check if we have billboard for that particular mile . If not , copy the previous maximum revenue . ; we do have billboard for this mile . ; If current position is less than or equal to t , then we can have only one billboard . ; Else we may have to remove previously placed billboard ; Driver Code
def maxRevenue ( m , x , revenue , n , t ) : NEW_LINE INDENT maxRev = [ 0 ] * ( m + 1 ) NEW_LINE nxtbb = 0 ; NEW_LINE for i in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( nxtbb < n ) : NEW_LINE INDENT if ( x [ nxtbb ] != i ) : NEW_LINE INDENT maxRev [ i ] = maxRev [ i - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT if ( i <= t ) : NEW_LINE INDENT maxRev [ i ] = max ( maxRev [ i - 1 ] , revenue [ nxtbb ] ) NEW_LINE DEDENT else : NEW_LINE INDENT maxRev [ i ] = max ( maxRev [ i - t - 1 ] + revenue [ nxtbb ] , maxRev [ i - 1 ] ) ; NEW_LINE DEDENT nxtbb += 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT maxRev [ i ] = maxRev [ i - 1 ] NEW_LINE DEDENT DEDENT return maxRev [ m ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT m = 20 NEW_LINE x = [ 6 , 7 , 12 , 13 , 14 ] NEW_LINE revenue = [ 5 , 6 , 5 , 3 , 1 ] NEW_LINE n = len ( x ) NEW_LINE t = 5 NEW_LINE print ( maxRevenue ( m , x , revenue , n , t ) ) NEW_LINE DEDENT