Plzzz help with this algorithim question: You were planning to study real hard t

Question

Plzzz help with this algorithim question:

You were planning to study real hard this quarter so you took out n books on java.
However you had better planning than execution and you have not read a single book
and they are now all overdue. The library charges one dollar a day for each overdue book.
You have calculated for each book the number of days it will take you to read the book.
You want to know what order to read (and return) the n books so that your overdue costs
are minimized.

Prove your greedy algorithm is correct using Java pseudocode.

Explanation / Answer

so consider 3 books taken from library.
as we know each bookcosts $1 for each book.
consider Book_A requires 4 days
Book_B requires 2 days
Book_c requires 6 days

the number of days left for exam is 7 days...
so what we have to choose...? obviously book A and B.

If allowed fractional..then A(4) and B(2)

-----------------------*********************--------------------------
GreedyKnapsack (m, n)
//profits and weights are arrays contain the profits and weights
// n objects ordered such that profits[i]/weights[i] >= profits[i+1]/weights[i+1]
// that is in non-increasing order.
// m size of the knapsack that is our exm due date and z (solution vector)
for i < 1 to n do
z[i]<- 0
endFor
total <- m
for i ! 1 to n do
if (weights[i] <= total)
z[i] <- 1
total <- total-weights[i]
else break
Endif
endFor

if (i<=n) z[i] <- total/weights[i]

endGreedyKnapsack   

---------------------------------------------------------------------
as per algorithm we will prove our solution
m (size)=7
n(objects) = 3
first initliazing vector [0 0 0]
now total contains 7
weight[0] <=total =====>4 <=7 true ===>solution vector[ 1 0 0]
now total = 7-4 ==>3
weight[1] <=total =====>2 <=3 true ===>solution vector[ 1 1 0]
now total = 3-2 ==>1
next one..fractional part...total/weights[2]====>1/6

so solution vector is [ 1 1 1/6]
and total profit is / or total money to be paid is
[1 1 1/6]
[4 2 6]
so 4x1 +2x1 + 6x1/6] = 4+2+1 = $7

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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