Java: 0/1 Knapsack Problem

Level : Intermediate
Mentor: Shailendra Chauhan
Type : GuidedLab
Points : 10
Duration : 00:30:00

Lab Details

Problem Statement:

We are given N items where each item has some weight and profit associated with it. We are

also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The target is to

put the items into the bag such that the sum of profits associated with them is the maximum

possible.

Note: The constraint here is we can either put an item completely into the bag or cannot put it

at all [It is not possible to put a part of an item into the bag].

Input:

N = 3, W = 4, profit[] = {1, 2, 3}, weight[] = {4, 5, 1}

Output:

3
Here are two items which have weight less than or equal to 4. If we select the 
item with weight 4, the possible profit is 1. And if we select the item with 
weight 1, the possible profit is 3. So, the maximum possible profit is 3. Note 
that we cannot put both the items with weight 4 and 1 together as the capacity of 
the bag is 4.
Self-paced Membership
  • 22+ Courses
  • 750+ Hands-On Labs
  • 200+ Quick Notes
  • 55+ Skill Tests
  • 45+ Interview Q&A
  • 10+ Real-world Projects
  • Career Coaching
  • Email Support
Upto 66% OFF
KNOW MORE..

To get full access to all courses

Still have some questions? Let's discuss.
CONTACT US
Accept cookies & close this