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;i. 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 l from the j'th location. Determine an optimal ity relation for rj involving these quantities and use it to design a dynamic programming algorithm

Explanation / Answer

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.