The Knapsack problem


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).