There is an s miles long road, with n possible locations for advertisements at d
ID: 3734242 • Letter: T
Question
There is an s miles long road, with n possible locations for advertisements at distances d1, . . . , dn from the beginning of the road. Putting an advertisement at the i’th location brings in revenue pi . Two advertisements cannot be located closer than distance ` from each other. Find a set of locations for the advertisement bringing in maximal revenue. a) Design a dynamic programming algorithm for this problem. b) Use your algorithm to find the optimal solution for distances 5, 9, 17, 23, revenues 4, 8, 6, 1 and distance 10. Hint: Let rj be the maximal revenue achievable by locations on the first j miles stretch of the road. For every j, let prev(j) be the location preceding dj which is at least distance ` from the j’th location. Determine an optimality relation for rj involving these quantities and use it to design a dynamic programming algorithm.
Explanation / Answer
#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));
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 based on x
if (x[nxtbb] != i)
maxRev[i] = maxRev[i-1];
// we do have billboard for this mile.
else
{
//Now we can either place the board or remove the board
// 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 have to maximise between twwo possible options either to place the board or not to.
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 = 30;
int x[] = {5, 9, 17, 23};
int revenue[] = {4,8,6, 1};
int n = sizeof(x)/sizeof(x[0]);
int t = 10;
cout << maxRevenue(m, x, revenue, n, t) << endl;
return 0;
}
b) optimal solution is : 10
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.