0-1 Knapsack Subset

general
1

Given number of items and maximum capacity…each item has corresponding id, profit and weight. How to find the subset in order to make the maximum possible profit using dp???
Please help me…to solve this question.

Input :

3 11
1 5 4
2 12 10
3 8 5

Output:
{1,3}
Explain : here 1st and 3rd items can be selected.
Peroblem link

1 Like
2

@rashedcs
Hey…I am also trying my hand over dp …
Can u please provide link of this problem

3

There are plenty of material already available on internet. Here are some of them:-

I hope this will be enough to boost your knowledge in Knapsack

1 Like
4

You can follow

Or you follow this video

If you face any problem, let me know

Hope it helps

5

hey @bansal , in this post, i want to know the subset of 0-1 knapsack in order to make the maximum possible profit …Please read this carefully…

6

Please find the subset of 0-1 knapsack in order to make the maximum possible profit …Please read this carefully…

7

I give a link of my problem.

8

I give a link of my problem.

9

I give a link of my problem.

10

https://studentnet.cs.manchester.ac.uk/ugt/COMP26120/lab/ex10.html

11

https://studentnet.cs.manchester.ac.uk/ugt/COMP26120/lab/ex10.html

12

https://studentnet.cs.manchester.ac.uk/ugt/COMP26120/lab/ex10.html

13

See this code - qpOqBv - Online C++0x Compiler & Debugging Tool - Ideone.com

14

Really nice…but how to track the items…

15

I have provided you full code with simple explanation. We just traversing back the path for getting the selected items

16

I know that in bottom up ,0-1 knapsack calculation table the first row and column will be zero …but your code it could not exists…Is it optional or mandatory???

17

its optimal.

18

Tnq so much @bansal12324.