5) There is an s miles long road, with n possible locations for advertisements a

Question

5) There is an s miles long road, with n possible locations for advertisements at distances di,...,dn from the beginning of the road. Putting an advertise- ment at the i'th location brings in revenue p Two advertisements cannot be located closer than distancel 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 r, be the maximal revenue achievable by locations on the first j miles stretch of the road. For every j, let prev(i) be the location preceding d, which is at least distance l from the j'th location. Determine an optimal- ity relation for r, involving these quantities and use it to design a dynamic programming algorithm.

Explanation / Answer

SOURCE CODE:

#include<bits/stdc++.h>                     

using namespace std;

int maxRevenue(int m, int x[], int revenue[], int n, int t)

{

int maxRev[m+1];

memset(maxRev, 0, sizeof(maxRev));

int nxtbb = 0;

for (int 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{nxbb]

maxRev[i-1]);

nxbb++;

}

}

else

maxRev[i] = maxRev[i - 1];

}

return maxRev[m];

}

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;

}

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.