Q1. You have 60million rupees for investment. There are five projects i.e. RoadC
ID: 3611624 • Letter: Q
Question
Q1. You have 60million rupees for investment. There are five projects i.e. RoadConstruction Program (P1), Punjab Irrigation Scheme (P2), Smallplant for Electricity production (P3),Educational SoftwareDevelopment Centre(P4) and Transport Facility in Urban Area (P5)where you can invest. If the cost of P1 is 10 million and profitearned is 7 million, the cost of P2 is 20 million and profit earnedis 14 million, the cost of P3 is 28 million and profit earned is 30million, and the cost of P4 is 22 million and profit earned is 28million. And cost of P5 is 40 million and profit earned is 50million. Determine the projects to be selected to earn the maximumprofit using 0-1 Knapsack Show completeprocess.
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
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.