Objective of The Knapsack Problem

1. 0-1 Knapsack Problem

Knapsack simply means bag. A bag of given capacity, C. We have to pack ‘N’ items into this bag. Every item has some weight and value. We have to ensure the total weight of items is less than or equal to a bag's capacity. At the same time, we have to maximise the value of items packed in the bag. 

This is the basics of the Knapsack problem. Now 0-1 Knapsack says you can either take the item as a whole or not, but you cannot break the item and take some part of it.

Sample Example

Example 1

Input: Knapsack Capacity, W = 25

{Value, Weight} pairs of item, array[] = {{10,10},{2,5},{6,8},{4,50},{100,1}}

Output: 118

Explanation: 

We will take items with values of 1kg, 10kg,8kg, and 5kg. So the total value will be equal to 100 + 10 + 6 + 2 = 118, which is the maximum possible value in a knapsack. Even if the Knapsack is not full, we won’t take the item with a weight of 50kg as it will exceed the capacity of the knapsack.

Example 2

Input: Knapsack Capacity, W = 6

{Value, Weight} pairs of item, array[] = {{1,10},{2,3},{2,2},{6,1},{4,5}}

Output: 10

Explanation: 

We will take items with a value of 1kg, 2kg, and 3kg, so the total value will be equal to 6 + 2 + 2 = 10, which is the maximum possible value in a knapsack.

Properties and Objective 

So, back to our topic, What is the objective of the knapsack problem? Well, you are given a set of items, each with a weight, a value, and a knapsack (container). The goal is to select a subset of items to maximise the total value of the chosen items. You need to make sure not to exceed the weight capacity of the knapsack. You will be choosing the item only once and as a whole. You can’t take any fraction or a part of it.

This problem is NP-complete. It is because solving this problem is the same as solving a subset sum problem, which is an NP-complete problem. It means the algorithm can be solved in polynomial time but have no efficient solution. There are several approximate algorithms that can solve it in a reasonable amount of time, such as dynamic programming, greedy algorithms, and branch and bound.

Methodology Followed

After knowing what is the objective of the knapsack problem. Let’s have a look at its methodology. The steps of methods you can follow to find its solution are:

• Step 1 Create a function that will accept the below parameters -
  • ‘W’ - is the weight of the knapsack. ‘values’ - is an array of item values. ‘weight’ - is an array of item weights. ‘N’ - number of items.
• Step 2: Create a 2D array of size ‘2 * W’.
• Step 3: Run an outer for loop with index ‘i’ varying from 0 to N.
• Step 4: Run an inner for loop with an index varying from 0 to W.
• Step 5:  If ‘i’ is even, then use the array’s 1st row else, the ‘0th’ row.
• Step 6: If the weight of the ‘ith’ item is higher than the current weight, exclude this item. Else, take the maximum value among the cases of including and excluding the item. 
• Step 7: Return the result.

You can refer to our article 0-1 Knapsack Problem to better understand about 0-1 Knapsack problem.

2. Fractional Knapsack Problem

The fractional knapsack problem is a type of knapsack problem where taking fractional values is allowed. This is a ‘greedy’ type that allows items to be divided if the bag’s capacity doesn’t allow the entire item. 

For example, if ‘W’ is 20 kg and the bag is filled up to 16 kg, an 8 kg item cannot be added to it. In this case, a fractional knapsack would allow just a fraction of the item to be added (4 kg here) and divide its value accordingly (dividing by half in this case).

Sample Examples

Example 1

Input: Knapsack Capacity, W = 25

{Value, Weight} pairs of item, array[] = {{10,10},{2,5},{6,8},{4,50},{100,1}}

Output: 118.08

Explanation: 

We will take items with weights 1kg, 10kg,8kg, 5kg and 1/50 fraction of 50kg, so the total value will be equal to 100 + 10 + 6 + 2 + (1/50)*4 = 118.08, which is maximum possible value in a knapsack.

Example 2

Input: Knapsack Capacity, W = 6

{Value, Weight} pairs of item, array[] = {{1,10},{2,3},{2,2},{6,1},{4,5}}

Output: 10.4 

Explanation: 

We will take items with weights of 1kg, 2kg, and 3/5 fraction of 5kg, so the total value will be equal to 6 + 2 +3/5 *(4) = 10.4, which is the maximum possible value in a knapsack.

Properties and Objective 

Talking about what is the objective of the knapsack problem here. You are given a set of n items, each with a weight w_i and a value v_i, and a knapsack with a maximum weight capacity of W. The goal is to select a set of items x_i such that

The property of the problem states that this problem can be best solved using a greedy algorithm. At each step, the item with the highest value-to-weight ratio is chosen. It is added until the knapsack is full.

Methodology Followed

After knowing what is the objective of the knapsack problem. Let’s have a look at its methodology. The steps of methods you can follow to find its solution are:

• Sort the array in decreasing order using the value/weight ratio. 
• Start taking the element having the maximum value/weight ratio.
• If the weight of the current item is less than the current knapsack capacity, add the whole item, or else add the portion of the item to the knapsack. 
• Stop adding the elements when the capacity of the knapsack becomes 0.
• Now we will have the maximum possible value in a knapsack. 

You can refer to our article Fractional Knapsack Problem to better understand about Fractional Knapsack problem.

3. Unbounded Knapsack

The unbounded knapsack can only take items as a whole, not parts or fractions. 

However, an item first picked for the knapsack can be chosen again in the next iteration. 

The only difference between the code for 0-1 and unbounded knapsack would be that the already picked elements won’t be considered the second time in the case of 0-1 knapsack. Still, the entire array will be considered all over again for an unbounded knapsack.

Sample Example

Example 1

Input: Knapsack Capacity, W = 25

{Value, Weight} pairs of item, array[] = {{10,10},{2,5},{6,8},{4,50},{100,1}}

Output: 2500

Explanation: 

We will take the item with a weight of 1kg 25 times, so the total value will be equal to 100*25 = 2500, which is the maximum possible value in a knapsack.

Example 2

Input: Knapsack Capacity, W = 6

{Value, Weight} pairs of item, array[] = {{1,10},{2,3},{2,2},{6,1},{4,5}}

Output: 36 

Explanation: 

We will take the item with a weight of 1kg 6 times, so the total value will be equal to 6*6 = 36, which is the maximum possible value of the knapsack.

Properties and Objective 

For an unbounded knapsack, what is the objective of the knapsack problem? Well, you are given a set of n items, each with a weight w_i and a value v_i, and a knapsack with a maximum weight capacity of W. The goal is to select a set of items x_i such that

This problem can be solved using a dynamic programming algorithm. Here, a table is built to store the maximum value that can be obtained for each weight.

This problem is a bit easier than the 0-1 knapsack problem. It can also be used in the same type of real-world applications such as logistics, manufacturing and resource allocation. However, it is important to note that the results of this problem may not be integers, unlike the 0-1 knapsack problem.

Methodology Followed

After knowing what is the objective of the knapsack problem. Let’s have a look at its methodology. The steps of methods you can follow to find its solution are:

• In a function, initialise a 2D array of size (N + 1) * (C + 1) and call the recursive function that takes the following values: 
  • ‘C’ - is the weight of the knapsack. ‘value’ - is an array containing the value of items. ‘weight’ - is an array to store the weight of the item, and ‘N’ is the number of items.
• The base case will be if ‘N’ = 0 or ‘C’ = 0, then return 0. 
• Next, check if the value is present in the array. If yes, then return the value.
• After that, check if the weight of the ‘Nth’ item is more than the current weight ‘C’. Then recursively call the same function for ‘N - 1’ items and ‘C’ weight. Assign it to array[N][C] and return the result.
• Else, get the maximum of the last two steps, assign the result to array[N][C], and return it.
• Call the recursive function for ‘N - 1’ and ‘C’ - weight[N].
• Finally, call the recursive function for ‘N - 1’ items with ‘C’ weight.

You can refer to our article Unbounded Knapsack to better understand about Unbounded Knapsack problem. 

Variations in The Knapsack Problem

After knowing what is the objective of the knapsack problem, let’s see its variation. There are several variations of the knapsack problem. Each with its own set of constraints and objectives. Some of the variations include:

1. 0-1 Knapsack problem: Here, each item can only be included in the knapsack once. Either in its entir ety or not at all.
2. Multiple knapsack problem: Here, there are multiple knapsacks with different capacities and constraints. The goal is to divide a set of items among the knapsacks to maximise the total value. While not exceeding the weight capacities of the knapsacks.
3. Bounded knapsack problem: Here, there is a restriction on the number of times an item can be chosen. Unlike the unbounded knapsack problem, where there is no restriction.
4. Fractional knapsack problem: Here, it is allowed to take a fraction of an item rather than just taking the whole item or not taking it at all.
5. Multiple-choice knapsack problem: Here, we are allowed to select multiple items from a given set of items.
6. Knapsack problem with profit and penalty: A penalty is associated with not choosing an item, and a profit is associated with choosing it.
7. Knapsack problem with multiple objectives: There is more than one objective to be optimised such as minimizing the cost (or weight) and maximizing the value.
8. Knapsack problem with precedence constraints: Some items must be included in the knapsack before others.

These are just a few examples of the many variations of the knapsack problem, and each variation can be applied to different real-world scenarios.

Check out this problem - Count Ways To Reach The Nth Stair 

Frequently Asked Questions

What is the difference between a 0-1 knapsack and a fractional knapsack?

In 0-1 Knapsack, we can either take the item or not. We are not allowed to break the item. While in the case of fractional knapsack, we are allowed to break the items to maximise the profit. 

What is the difference between an unbounded knapsack and a 0-1 knapsack?

The only difference between 0-1 Knapsack and Unbounded Knapsack is that in 0-1 knapsack, you can utilise an item only once. While in the unbounded knapsack, you may utilise an infinite number of items.

What is a multiple knapsack problem?

This is a generalisation of the standard knapsack problem from 1 to ‘M’ knapsacks which might have different capacities. Here, you have multiple knapsacks with different capacities and constraints. The goal is to divide a set of items among the knapsacks to maximise the total value. While not exceeding the weight capacities of the knapsacks.

Can 0-1 Knapsack be solved using the greedy approach?

Yes, 0-1 knapsack can be solved using the greedy approach. But it won’t be of the best complexity. It is solved using a dynamic programming approach for the best time and space complexity. 

Conclusion

This article discussed what is the objective of the knapsack problem. We discussed the problem along with its properties, objectives, methodologies and variations. We hope this blog has helped you know what is the objective of the knapsack problem. 

Refer to our Guided Path on Code360 to upskill yourself in Data Structures and Algorithms, Competitive Programming and many more! If you wish to test your competency in coding, check out the mock test series and take part in the contests.

If you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problems, interview experiences, and interview bundles.