The Knapsack problem is an example of the combinational optimization problem. This problem is also commonly known as the “Rucksack Problem“. The name of the problem is defined from the maximization problem as mentioned below:

Given a bag with maximum weight capacity of W and a set of items, each having a weight and a value associated with it. Decide the number of each item to take in a collection such that the total weight is less than the capacity and the total value is maximized.

Types of Knapsack Problem:

The knapsack problem can be classified into the following types:

1. Fractional Knapsack Problem
2. 0/1 Knapsack Problem
3. Bounded Knapsack Problem
4. Unbounded Knapsack Problem

1. Fractional Knapsack Problem

The Fractional Knapsack problem can be defined as follows:

Given the weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.