Highway Billboard Problem | PHP 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
< ? php function maxRevenue ( $ m , $ x , $ revenue , $ n , $ t ) { $ maxRev = array_fill ( 0 , $ m + 1 , false ) ; $ nxtbb = 0 ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) { if ( $ nxtbb < $ n ) { if ( $ x [ $ nxtbb ] != $ i ) $ maxRev [ $ i ] = $ maxRev [ $ i - 1 ] ; else { if ( $ i <= $ t ) $ maxRev [ $ i ] = max ( $ maxRev [ $ i - 1 ] , $ revenue [ $ nxtbb ] ) ; else $ maxRev [ $ i ] = max ( $ maxRev [ $ i - $ t - 1 ] + $ revenue [ $ nxtbb ] , $ maxRev [ $ i - 1 ] ) ; $ nxtbb ++ ; } } else $ maxRev [ $ i ] = $ maxRev [ $ i - 1 ] ; } return $ maxRev [ $ m ] ; } $ m = 20 ; $ x = array ( 6 , 7 , 12 , 13 , 14 ) ; $ revenue = array ( 5 , 6 , 5 , 3 , 1 ) ; $ n = sizeof ( $ x ) ; $ t = 5 ; echo maxRevenue ( $ m , $ x , $ revenue , $ n , $ t ) ; ? >