算法设计（公路广告牌问题解决和代码实现）

本文概述

C ++
Java
Python3
C#
的PHP

考虑一条高速公路中号英里。任务是在高速公路上放置广告牌, 以使收入最大化。广告牌可能的位置由数字给出X1< x2< ….. < xn-1< x?, 以从路段的一端开始的英里为单位指定位置。如果我们将广告牌放置在位置x一世, 我们获得了[R一世> 0。有一个限制, 即不能在其中放置两个广告牌?英里以下。
注意：所有来自x的网站1到x?需要在M英里的高速公路上放置广告牌, 范围是0到M。
【算法设计（公路广告牌问题解决和代码实现）】例子：

Input : M = 20 x[]= {6, 7, 12, 13, 14} revenue[] = {5, 6, 5, 3, 1} t = 5 Output: 10 By placing two billboards at 6 miles and 12 miles will produce the maximum revenue of 10.Input : M = 15 x[] = {6, 9, 12, 14} revenue[] = {5, 6, 3, 7} t = 2 Output : 18

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。令maxRev [i], 1 < = i < = M, 是从高速公路开始到i英里所产生的最大收益。现在, 对于高速公路上的每一英里, 我们需要检查该英里是否可以选择任何广告牌, 否则, 直到该英里之前产生的最大收入将与直到一英里之前产生的最大收入相同。但是, 如果该英里有广告牌选项, 那么我们有2个选项：
1.我们要么放置广告牌, 要么忽略前t英里内的广告牌, 然后添加所放置广告牌的收入。
2.忽略此广告牌。因此, maxRev [i] = max(maxRev [i-t-1] +收入[i], maxRev [i-1])
以下是此方法的实现：
C ++

// C++ program to find maximum revenue by placing // billboard on the highway with given constarints. #include< bits/stdc++.h> using namespace std; int maxRevenue( int m, int x[], int revenue[], int n, int t) { // Array to store maximum revenue at each miles. int maxRev[m+1]; memset (maxRev, 0, sizeof (maxRev)); // actual minimum distance between 2 billboards. int nxtbb = 0; for ( int i = 1; i < = m; i++) { // check if all billboards are already placed. if (nxtbb < n) { // check if we have billboard for that particular // mile. If not, copy the previous maximum revenue. if (x[nxtbb] != i) maxRev[i] = maxRev[i-1]; // we do have billboard for this mile. else { // We have 2 options, we either take current // or we ignore current billboard.// If current position is less than or equal to // t, then we can have only one billboard. if (i < = t) maxRev[i] = max(maxRev[i-1], revenue[nxtbb]); // Else we may have to remove previously placed // billboard else maxRev[i] = max(maxRev[i-t-1]+revenue[nxtbb], maxRev[i-1]); nxtbb++; } } else maxRev[i] = maxRev[i - 1]; }return maxRev[m]; }// Driven Program int main() { int m = 20; int x[] = {6, 7, 12, 13, 14}; int revenue[] = {5, 6, 5, 3, 1}; int n = sizeof (x)/ sizeof (x[0]); int t = 5; cout < < maxRevenue(m, x, revenue, n, t) < < endl; return 0; }

Java

// Java program to find maximum revenue // by placing billboard on the highway // with given constarints.class GFG { static int maxRevenue( int m, int [] x, int [] revenue, int n, int t) { // Array to store maximum revenue // at each miles. int [] maxRev = new int [m + 1 ]; for ( int i = 0 ; i < m + 1 ; i++) maxRev[i] = 0 ; // actual minimum distance between // 2 billboards. int nxtbb = 0 ; for ( int i = 1 ; i < = m; i++) { // check if all billboards are // already placed. if (nxtbb < n) { // check if we have billboard for // that particular mile. If not, // copy the previous maximum revenue. if (x[nxtbb] != i) maxRev[i] = maxRev[i - 1 ]; // we do have billboard for this mile. else { // We have 2 options, we either take // current or we ignore current billboard. // If current position is less than or // equal to t, then we can have only // one billboard. if (i < = t) maxRev[i] = Math.max(maxRev[i - 1 ], revenue[nxtbb]); // Else we may have to remove // previously placed billboard else maxRev[i] = Math.max(maxRev[i - t - 1 ] + revenue[nxtbb], maxRev[i - 1 ]); nxtbb++; } } else maxRev[i] = maxRev[i - 1 ]; } return maxRev[m]; } // Driver Code public static void main(String []args) { int m = 20 ; int [] x = new int []{ 6 , 7 , 12 , 13 , 14 }; int [] revenue = new int []{ 5 , 6 , 5 , 3 , 1 }; int n = x.length; int t = 5 ; System.out.println(maxRevenue(m, x, revenue, n, t)); } }// This code is contributed by Ita_c.

Python3

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

// C# program to find maximum revenue // by placing billboard on the highway // with given constarints. using System; class GFG { static int maxRevenue( int m, int [] x, int [] revenue, int n, int t) { // Array to store maximum revenue // at each miles. int [] maxRev = new int [m + 1]; for ( int i = 0; i < m + 1; i++) maxRev[i] = 0; // actual minimum distance between // 2 billboards. int nxtbb = 0; for ( int i = 1; i < = m; i++) { // check if all billboards are // already placed. if (nxtbb < n) { // check if we have billboard for // that particular mile. If not, // copy the previous maximum revenue. if (x[nxtbb] != i) maxRev[i] = maxRev[i - 1]; // we do have billboard for this mile. else { // We have 2 options, we either take // current or we ignore current billboard. // If current position is less than or // equal to t, then we can have only // one billboard. if (i < = t) maxRev[i] = Math.Max(maxRev[i - 1], revenue[nxtbb]); // Else we may have to remove // previously placed billboard else maxRev[i] = Math.Max(maxRev[i - t - 1] + revenue[nxtbb], maxRev[i - 1]); nxtbb++; } } else maxRev[i] = maxRev[i - 1]; } return maxRev[m]; } // Driver Code static void Main() { int m = 20; int [] x = new int []{6, 7, 12, 13, 14}; int [] revenue = new int []{5, 6, 5, 3, 1}; int n = x.Length; int t = 5; Console.Write(maxRevenue(m, x, revenue, n, t)); } }// This code is contributed by DrRoot_

的PHP

< ?php // PHP program to find // maximum revenue by // placing billboard on // the highway with given // constraints.function maxRevenue( $m , $x , $revenue , $n , $t ){ // Array to store maximum // revenue at each miles. $maxRev = array_fill (0, $m + 1, false); // actual minimum distance // between 2 billboards. $nxtbb = 0; for ( $i = 1; $i < = $m ; $i ++) { // check if all billboards // are already placed. if ( $nxtbb < $n ) { // check if we have billboard // for that particular // mile. If not, copy the // previous maximum revenue. if ( $x [ $nxtbb ] != $i ) $maxRev [ $i ] = $maxRev [ $i - 1]; // we do have billboard // for this mile. else { // We have 2 options, // we either take // current or we ignore // current billboard.// If current position is // less than or equal to // t, then we can have only // one billboard. if ( $i < = $t ) $maxRev [ $i ] = max( $maxRev [ $i - 1], $revenue [ $nxtbb ]); // Else we may have to // remove previously // placed billboard else $maxRev [ $i ] = max( $maxRev [ $i - $t - 1] + $revenue [ $nxtbb ], $maxRev [ $i - 1]); $nxtbb ++; } } else $maxRev [ $i ] = $maxRev [ $i - 1]; }return $maxRev [ $m ]; }// Driver Code $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 ); // This code is contributed by ajit ?>

输出如下：

10

时间复杂度：O(M), 其中M是公路总距离。
辅助空间：O(M)。
资源：
https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture18/Lecture18.pdf
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。