Help me to solve this: You have 60 million rupees for investment. There are five
ID: 3611630 • Letter: H
Question
Help me to solve this:You have 60 million rupees for investment. There are five projectsi.e. Road Construction Program (P1), Punjab Irrigation Scheme (P2),Small plant 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 complete process. Thanks Help me to solve this:
You have 60 million rupees for investment. There are five projectsi.e. Road Construction Program (P1), Punjab Irrigation Scheme (P2),Small plant 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 complete process. Thanks Thanks
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.