The Knapsack problem (BKP) is a problem in combinatorial optimization.
computer science
Description
PART 1
The Knapsack problem (BKP) is a problem in combinatorial optimization. This problem is described as
follows:
Given a list of items, each item has a weight and a benefit, determine the number of each item to
include in a bag so that the total weight is less or equal to the limit of the bag and we get the
maximum benefit.
The most common problem to solve is the 0-1 knapsack problem, which restricts the number of
copies of an item to one. Therefore, an item can be inside the bag or outside.
We now consider the problem with a set of items (you can find the document in canvas with the
name “assignment 1 knapsack.txt”).These items are represented by 2 values (weight and benefit) as
illustrated in the table below.
What to do: Your assignment now is to apply Breadth-first search (BFS) and Depth-first search (DFS)
to search for the best combination of items inside the bag. Remember, only one copy of an item.
You need to use a tree (queue or stack depending of the algorithm) and nodes in order to implement
both search strategies. You need to present both codes to the teacher. (0.5 points each code).
Pre-conditions in order to present your code:
- The codes should run faster than 0.5 seconds. If you cannot get it faster, talk to the teacher. The reason could be your computer.
- You must use queue or stack, depending of the algorithm (or simulate them using an
array).
