0 Minni Asked: October 17, 20222022-10-17T09:37:59+05:30 2022-10-17T09:37:59+05:30In: Data ScienceSolve using fractional knapsack: M=20, n=4 P= (3, 10, 15, …0Solve using fractional knapsack:M=20, n=4P= (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 ShareFacebook1 AnswerVotedOldestRecent 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 takenprofitweightRemaining weightO315128O210130O4580O1350 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 >