You have 60 million rupees for investment. There arefive projects i.e. Road Cons
ID: 3611623 • Letter: Y
Question
You have 60 million rupees for investment. There arefive projects i.e. Road Construction Program (P1), PunjabIrrigation Scheme (P2), Small plant for Electricity production(P3),Educational Software Development Centre(P4) and TransportFacility in Urban Area (P5) where you can invest. If the cost of P1is 10 million and profit earned is 7 million, the cost of P2 is 20million and profit earned is 14 million, the cost of P3 is 28million and profit earned is 30 million, and the cost of P4 is 22million and profit earned is 28 million. And cost of P5 is 40million and profit earned is 50 million. Determine the projects tobe selected to earn the maximum profit using 0-1 Knapsack Showcomplete process.Explanation / Answer
Greedy by Profit
At each step select from the remaining items the one with thehighest profit (provided the capacity of the knapsack is notexceeded). This approach tries to maximize the profit by choosingthe most profitable items first.
Greedy by Weight (investment)
At each step select from the remaining items the one with theleast investment (provided the capacity of the knapsack is notexceeded). This approach tries to maximize the profit by putting asmany items into the knapsack as possible.
Greedy by Profit Density
greedy by
item
Investment
(in millions)
Profit
(in millions)
Profit/investment
profit
investment
density
optimal solution
P1
10
7
0.7
0
1
0
1
P2
20
14
0.7
0
1
0
0
P3
28
30
1.07
0
1
1
1
P4
22
28
1.27
0
0
1
1
P5
40
50
1.25
1
0
0
0
total weight(in millions)
40
58
50
60
total profit(in millions)
50
51
58
65
Total capacity=60 millions
From the above considerations we can say that, by choosing theprojects P1, P3 and p4 we can get a maximum profit of 65 millionsfrom an investment of 60 millions.
greedy by
item
Investment
(in millions)
Profit
(in millions)
Profit/investment
profit
investment
density
optimal solution
P1
10
7
0.7
0
1
0
1
P2
20
14
0.7
0
1
0
0
P3
28
30
1.07
0
1
1
1
P4
22
28
1.27
0
0
1
1
P5
40
50
1.25
1
0
0
0
total weight(in millions)
40
58
50
60
total profit(in millions)
50
51
58
65
Total capacity=60 millions
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.