A fast food company is considering a bunch of bids to open franchises on a road

Question

A fast food company is considering a bunch of bids to open franchises on a road and they want to develop an algorithm to decide which to accept. For each of the n miles along the road, the bid for that location is recorded (if there is no bid it is recorded as 0). The company wants to accept the bids which maximizes their total earnings. One extra caveat is that two franchises must be at least 3 miles apart (for example if you accept the bid at mile 5 then you can't accept the bids at miles 3, 4, 6, 7). Example: For the bids given above, which would you accept to maximize the earnings? (in this case, n = 9) Let E(n) denote your maximum earnings for the bids in the first n miles. Give a recursive definition of E: Base case Recursive case Give pseudo-code for an algorithm which uses memorization to compute E(n) based on the above recurrence (assume you are passed an array b of the bids).

Explanation / Answer

1) from the given bids accecpt the bid which has maximum amount, here for n=9 , bid ammount is 60000 which is maximum.
2)
for finding the maximum ammount
from bid, use recursive function.
and each function should return the max ammount, it could get by selecting that bid.

find MAx of all such function calls.

E(i)={

0 | if i=0

return ARRAY_BID[i] + MAX { E(i+3), E(i+4), E(i+5), ........E(n) } | if i > 0

}

3)

for(i=0 to n)
{
array_bids[n];
amount=countMAX(i,0,array_bids);
if(amount>maxAmount)
{
maxAmount=amount;
}
}

int countMAX(int cur,int cur_bid,int [] array_bids)
{

for(j=cur+3,j<=n;j++)
{
bid=countMAX(cur+3,cur_bid+bidValueat[cur+3],array_bids)
if(bid>max_bid){
max_bid=bid;
}
}
return cur_bid+max_bid;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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