The Gateway to Computer Science Excellence

+5 votes

Best answer

In case of fractional knapsack we apply greedy technique.We calculate P_{i} / W_{i} for each item

So,

P_{1 }/ W_{1} = 70 / 10 = 7

P_{2}_{ }/ W_{2} = 25 / 1 = 25

P_{3} / W_{3} = 15 / 2 = 7.5

P_{4 }/ W_{4} = 29 / 2 = 14.5

P_{5} / W_{5} = 38 / 6 = 6.33

So now we select the processes giving priority to one having larger profit by weight ratio.

So P_{2 }is selected first

Profit = 25

Weight remaining = 14 - 1 = 13

Then P_{4} is selected , so

profit = 25 + 29 = 54

weight remaining = 13 - 2 = 11

Then P_{3} is selected

So profit = 54 + 15 = 69

weight remaining = 11 - 2 = 9

Then P_{1} is selected .

But remaining weight = 9 and its weight = 10 , so we consider the profit of (9/10) th part only

So profit = 69 + 9/10 * 70

= 69 + 63

= 132

**Hence maximum profit achievable using fractional knapsack = 132**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,691 answers

199,329 comments

107,351 users