a) Given a list S of special days, describe a greedy algorithm that minimises th
ID: 3911693 • Letter: A
Question
a) Given a list S of special days, describe a greedy algorithm that minimises the number of dinners that you must treat your partner. After all, you are very busy with your
studies and cannot aord to take many evenings o. Your algorithm's output should be a set of days on which you go out for dinner.
b) Give a moderately-sized (n=7) instance, showing the dates where your greedy solution schedules the dinners, and some alternate solution which schedules more dinners. A
diagram may be helpful in illustrating your instance and solutions.
c) Give a proof that your greedy approach produces an optimal solution.
"You are such a cheapskate!'" Suppose that your significant other has a list of n "special days, S-(s, ,%) for Each special day si has associated with it: . a: the actual date. You should buy the dinner on or after this date to earn credit for s, which you are expected to treat him/her to dinner. . di: the deadline. You MUST buy your partner dinner for s on or before this date, otherwise you will suffer the unspeakable consequences ·Vi: the cost value of the dinner your partner expects you to pay, in dollars You have a per-dinner budget of B dollars. Assume that 0Explanation / Answer
Ans1-
firstly both should be sorted in opposite order
then
i=0;
j=0;
for(;i<n && j<n;)
{
while(a[i]<day)
i++;
while(b[j]>day)
j++;
count++;
}
Ans 2-
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i]<day && b[j]>day)
{
m=B-v[j];
B+=m
count++;
}
Ans 3-
my solution is optimum in first answer as before max deadline and after min actual date is the minimum
and in second case every time when you lie between deadline and actual date there is a treat
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.