In this assignment you are going to use one algorithm each from Brute Force, Divide & Conquer, Greedy algorithms and Dynamic Programming to solve the Knapsack Problem where one must maximize the benefit of items in a knapsack without extending its capacity. The main goal of this assignment is to compare the results of these algorithms and find the best one.

Knapsack Problem:

The problem is to determine the optimal selection of packages for a customer shopping in a supermarket, given a set of nn packages with associated weights (W[i]) and values (V[i]). Each package ii has a weight W[i]100 and a value V[i]100. The customer has a maximum weight carrying capacity of M100. The objective is to identify the subset of packages that the customer should take away to maximize the total value, subject to the constraint that the total weight does not exceed the customer's carrying capacity.

Assumptions:

The number of packages (n) is less than or equal to 100.

Each package has a weight (W[i]) and a value (V[i]), both of which are less than or equal to 100.

The customer's carrying capacity (M) is less than or equal to 100.

The weights and values of the packages are non-negative integers.

The customer cannot partially take a package; it's either taken in its entirety or not at all.

The goal is to maximize the total value of the selected packages.

Output:

The solution to the problem involves determining the specific packages that the customer should take away to achieve the maximum total value while adhering to the weight constraint. The deliverables would include:

The list of selected packages that the customer should take.

The total value of the selected packages.

Verification that the total weight of the selected packages does not exceed the customer's carrying capacity.

The solution may be presented as an algorithm or a set of instructions that outline the decision-making process for selecting packages, along with the final result of the selected packages and their total value.

Tasks

The problem will cover three tasks:

The first task is to illustrate the related design techniques (Brute Force, Divide & Conquer, Greedy algorithms and Dynamic Programming) to solve the knapsack problem.

[CLO1, PLO1, C2]

The second task should include the design and implementation of the related Brute Force, Divide & Conquer, Greedy and Dynamic Programming algorithms.

[CLO3, PLO4, C6]

The third task should include the analysis and evaluation of the results of these algorithms and find the best one.

[CLO2, PLO3, C4]

Only make a graph or some diagrams to proove that dynamic programming approach is the best one from all other approaches.