The constraints are as follows If you conduct a basic course in week x, then you

Question

The constraints are as follows If you conduct a basic course in week x, then you get an instructor fee of bx > 0 dollars; if you conduct an advanced course, you get an instructor fee of ax > 0 dollars However, if you conduct an advance course in week x, you are required to spend a week for the course preparation. Therefore, you do not conduct any course in week x1 Consider a sequence of n weeks, you are given a choice of "basic," "advanced," or "none" for each of the n weeks, with the constraint that if "advanced" is chosen for week x > 1, then "none has to be chosen for week x-1. You are allowed to choose an advanced course to conduct in week 1. The total instructor fees that you earn for a duration of n weeks is determined as follows for each x, you add bx to your instruction fee if you choose "basic" in week x, and you add a to your instruction fee if you choose "advanced" in week x. You add 0 if you choose "none" in week Given sets of instructor fees b1, b2, , bn and al, az, , an, your task is tofind an optimal course selection that maximises the total instruction fee for a duration ofn weeks Week 1 S 1000 S 2000 Table 1 Week 2 $ 800 S 4000 Week 3 S 500 1000 Week 4 S 1000 S 800 al For example, Table l shows a 4-week courses and the corresponding instructor fees b1, b2, b3,b4 and a1, a2, ??, a4. The optimal selection would be "none" (week 1), "advanced" (week 2), "basic (week 3), and "basic" (week 4). The maximum total instruction fees would be 04000500 + 1000 5500 dollars. . Design an efficient algorithm that solves this problem. Your algorithm should output the selection for each week and the maximum total instruction fees. Write pseudocode of the algorithm. Analyse time efficiency of the algorithm . .Implement your designed algorithm in C/C++. Specify your assumptions, data structure used in the implementation.

Explanation / Answer

Algorithm

(1)Declare an arr [week+1] where arr[i] stores maximum instructor fee upto ith week and arr[0]=0;

(2) for i=1......week

if i=1 maximum of basic fee b[0] and advance fee a[0] ;

else arr[i]=maximum (arr[i-1]+b[i-1],arr[i-2]+a[i-1]); //skiping a day for advance course preparation(arr[i-2])

(3)print value of arr[week] gives the maximum instructor fee.

#include<iostream>

using namespace std;

int max_(int a,int b){

return a>b?a:b;

}

int main(){

cout<<"Enter number of weeks : ";

int week;

cin>>week;

int arr[week+1],b[week],a[week];

arr[0]=0;

cout<<"Enter Basic course fee per week ";

for(int i=0;i<week;i++)cin>>b[i];

cout<<"Enter Advance course fee per week ";

for(int i=0;i<week;i++)cin>>a[i];

for(int i=1;i<=week;i++){

if(i==1)arr[i]=max_(a[i-1],b[i-1]);

else if(i>1)arr[i]=max_(arr[i-1]+b[i-1],arr[i-2]+a[i-1]);

}

for(int i=1;i<=week;i++){

cout<<"week"<<i<<" fee : "<<arr[i]<<" ";

}

cout<<"maximum instructor fee : "<<arr[week]<<" ";

return 0;

}

As,only one loop is running therefore complexity will be O (number_of_weeks);

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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