greedy method

Greedy Method

1) Making Change
Greedy method selects the largest change nearest to the required amount.
For example :
change: $10, $5, $1
required amount: $18
Greedy method will first choose $10, then $5 and lastly 3 $1

2) Fractional Knapsack
For this part, you can just tear the notes and throw it into the dustbin.
Download the knapsack.ppt at mmlscyber (it contains some pages of the textbook)

Following the slide (knapsack.ppt) example:
We first calculate the ratio priority
p/w for each chapter. (p->importance value, w->pages)

Knapsack selects the pages from the chapter following the priority ratio. From the highest ratio to the lowest. So knapsack with select the pages from chap4, 1, 2, 5, 3.

However adding all the pages from chap4, 1, 2, 5 already accumulates total 560 pages. The required amount is 600 pages. So we could not add all of the 200 pages from chap 3. Instead we pick 40pages from chap3.

You can refer to the slides mentioned to study how to calculate profits.