A craftsman makes several different products. The amount he earns for making eac

Question

A craftsman makes several different products. The amount he earns for making each type of product, and the time he will spend making them is shown in the following table. 4a duration (hours) 1 2 3 5 7 8 earned1 6 8 12 15 20 The craftsman has an 8-hour day to plan. Using a dynamic programming approach, compute his maximum possible earnings. Explain your method and show the intermediate amounts computed. b The Fibonacci numbers are defined as follows: Fo 0 F, = Fi-1 +Fi-2, when i > 1 i) Write an algorithm to compute Fibonacci number Fn using a top-down ursive) dynamic programming approach. You can use either Java or pseudocode. Write an algorithm to compute Fibonacci number Fn using a bottom-up (iterative) dynamic programming approach. You can use either Java or pseudocode ii)

Explanation / Answer

Prob 4a

Idea

let us say we have an "n" hour day to plan, the approach using dynamic programming would be something like

f(n)=max{ a[n], f(1)+f(n-1) , f(2)+f(n-2) , .......f(n/2)+f(n/2)}

Here f(n) is the maximum the craftsman can earn for an n hour day and a[n] is the input matrix,we will keep storing the values of f(n) from 1 to n

this type of solution would have a space complexity of O(n) and time complexity of O(n^2)

for this example we have:

a={0,1,6,8,0,12,,0,15,20} (a[0] is defined to be 0, a[4] and a[6] are 0 because there values are missing)

let's call our solution array to be F and initialize F[0]=0 and F[1]=a[1]

F[2]=max(a[2],F[1]+F[1])=max(6,1+1)=max(6,2)=6

F[3]=max(a[3],F[1]+F[2])=max(8,6+1)=8

F[4]=max(a[4],F[1]+F[3],F[2]+F[2])=max(0,9,12)=12

F[5]=max(a[5],F[1]+F[4],F[2]+F[3])=max(12,13,14)=14

F[6]=max(a[6],F[1]+F[5],F[2]+F[4],F[3]+F[3])=max(0,15,18,16)=18

F[7]=max(a[7],F[1]+F[6],F[2]+F[5],F[3]+F[4])=max(15,19,20,20)=20

F[8]=max(a[8],F[1]+F[7],F[2]+F[6],F[3]+F[5],F[4]+F[4])=max(20,21,24,22,24)=24

So the answer is 24.

Prob 4b

i) the top down version or recursive version using dynamic programming would basically mean a memoized version, wherein we would store and remember the fibonacci values already calculated so as to not solve same subproblem multiple times.

Pseudocode

// initialize fib with 0

int fib[n]={0};

int sol(int n)

{

if (fib[n] == 0)

{

if (n <= 1)

fib[n] = n; // for base value initialization

else

fib[n] = sol(n-1) + sol(n-2);

}

return fib[n];

}

consider solving for fib(3), since fib[3] is 0 it wil solve for sol(2)+sol(1). Now sol(2) comes first in the statement so it will call sol() with value 2 and then now since fib(2) is also 0 it will solve for sol(1)+sol(0).Now the call for sol(1) returns 1 and sol(0) returns 0 and fib(2) becomes 1+0=1 and this value is stored in fib.Now if a function call is ever made for value 2 it will be returned directly without solving for it again since it is not 0.

ii)

the second part is more straightforward, it just needs a for loop

pseudocode

int sol(int n)

{

int fib[n+1];

fib[0] = 0; fib[1] = 1; //initialize base values

for (int i = 2; i <= n; i++){

fib[i] = fib[i-1] + fib[i-2];

}

return f[n];

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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