0 0 Minni Asked: October 17, 20222022-10-17T09:37:59+05:30 2022-10-17T09:37:59+05:30In: Data Science Solve using fractional knapsack: M=20, n=4 P= (3, 10, 15, … 0 0 Solve using fractional knapsack: M=20, n=4 P= (3, 10, 15, 5) W= (5, 13, 12, 8). 101213155) w= (58).design and analysis of algorithmsn=4 p= (3solve using fractional knapsack: m=20 Share Facebook 1 Answer Voted Oldest Recent Saurav kumar 2022-10-17T18:23:31+05:30Added an answer on October 17, 2022 at 6:23 pm M=20 (total capacity of bag) N=4 (no of items) Let’s find Pi/Wi (profit/weight) for each items: P1/W1=3/5 = 0.60 (O1) P2/W2=10/13= 0.76(O2) P3/W3= 15/12 = 1.25 (O3) P4/W4 = 5/8 = 0.62 (O4) Where O is object no Let’s arrange them in order: 1.25 >> 0.76 >> 0.62 >> 0.60 Object taken profit weight Remaining weight O3 15 12 8 O2 10 13 0 O4 5 8 0 O1 3 5 0 Now, Knapsack weight left to be filled is 8 kg but item-2 has a weight of 13 kg. Since in fractional knapsack problem, even the fraction of any item can be taken. So, knapsack will contain the following items- < O3,(8/13)O2 > Leave an answerCancel replyYou must login to add an answer. Username or email* Password* Remember Me! Forgot Password?
M=20 (total capacity of bag)
N=4 (no of items)
Let’s find Pi/Wi (profit/weight) for each items:
P1/W1=3/5 = 0.60 (O1)
P2/W2=10/13= 0.76(O2)
P3/W3= 15/12 = 1.25 (O3)
P4/W4 = 5/8 = 0.62 (O4)
Where O is object no
Let’s arrange them in order: 1.25 >> 0.76 >> 0.62 >> 0.60
Object taken
profit
weight
Remaining weight
O3
15
12
8
O2
10
13
0
O4
5
8
0
O1
3
5
0
Now,
< O3,(8/13)O2 >