The Gateway to Computer Science Excellence
+1 vote
622 views

Number of Cateogires are 5, Thier total weights are 

w1,w2,w3,w4,w5={7,2,4,8,6}

b1,b2,b3,b4,b5={5,6,4,3,2}

M=6=Maximum Capacity= W

I am having confusion How to solve using dynamic approach 0/1 Dynamic Knapsack problem

Do we firstly need to arrande the weights in increasing order ??????????

in Algorithms by Active (3.7k points) | 622 views
+2
fractional knapsack needs sorting : 0/1 version does not
+2

table[x][y] = Optimum result when taking items only from $1$ to $x$ for a knapsack of current capacity $y$

In $0/1$ version dynamic state transitions are:

  1. include item i th when the weight of item i is less than current capacity w:
    •  table[i][w] = max(value[i] + K[i-1][w-Wt[i]],  table[i-1][w]);
  2. Else , Do not include item i th
    1.  table[i][w] = table[i-1][w]
0

I am solving Please tell whether i solved Correct or Wrong ?

0

What i am thinking that weight should be arranged in increasing order .

will it be wrong if i arrange in increasing/Ascending order ?

0
somebody please solve this in order to remove a big confusion please solve it please
0
My answer is coming Maximum wieght M=W=6 with value =(10)
0

rawkstar watch this

1 Answer

+2 votes
Maximum value: 10

we can take W3 and W4 so that the total value would be 6+4=10
by Junior (985 points)
0
year dear sir mine is also coming same so i hope it would be right :)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,654 questions
56,169 answers
193,877 comments
94,299 users