Horje
Introduction to Knapsack Problem, its Types and How to solve them

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.

Some practice problems on 0/1 Knapsack:

Sl. No.Problem
1Fractional Knapsack Problem
2Fractional Knapsack Queries
3Unbounded Fractional Knapsack

2. 0/1 Knapsack Problem

The 0/1 Knapsack problem can be defined as follows:

We are given N items where each item has some weight (wi) and value (vi) associated with it. We are also given a bag with capacity W. The target is to put the items into the bag such that the sum of values associated with them is the maximum possible.

Note that here we can either put an item completely into the bag or cannot put it at all.

Mathematically the problem can be expressed as:

Maximize [Tex]\sum_{i = 1}^{N}v_{i}x_{i}    [/Tex] subject to [Tex]\sum_{i = 1}^{N}w_{i}x_{i} \leq W    [/Tex] and xi ∈ {0, 1}

Some practice problems on 0/1 Knapsack:

Sl. No.Problem
10/1 Knapsack Problem
2Printing Items in 0/1 Knapsack
30/1 Knapsack Problem to print all possible solutions
4Knapsack with large Weights
50/1 knapsack queries
60/1 Knapsack using Branch and Bound
70/1 Knapsack using Least Cost Branch and Bound

Following are the differences between the 0/1 knapsack problem and the Fractional knapsack problem.

Sr. No

0/1 knapsack problem

Fractional knapsack problem

1.The 0/1 knapsack problem is solved using dynamic programming approach.Fractional knapsack problem is solved using a greedy approach.
2.In the 0/1 knapsack problem, we are not allowed to break items.Fractional knapsack problem, we can break items for maximizing the total value of the knapsack.
3. 0/1 knapsack problem, finds a most valuable subset item with a total value less than equal to weight.In the fractional knapsack problem, finds a most valuable subset item with a total value equal to the weight if the total weight of items is more than or equal to the knapsack capacity.
4. In the 0/1 knapsack problem we can take objects in an integer value.In the fractional knapsack problem, we can take objects in fractions in floating points. 

3. Bounded Knapsack Problem

The Bounded Knapsack problem can be defined as follows:

Given N items, each item having a given weight wi and a value vi, the task is to maximize the value by selecting a maximum of K items adding up to a maximum weight W.

Mathematically the problem can be expressed as:

Maximize [Tex]\sum_{i = 1}^{N}v_{i}x_{i}    [/Tex] subject to [Tex]\sum_{i = 1}^{N}w_{i}x_{i} \leq W    [/Tex] and xi ∈ {0, 1, . . . , K}

Some practice problems on Bounded Knapsack:

Sl. No.Problem
1Extended Knapsack Problem
2Partition Problem
3Count of subsets with sum equal to X
4Length of longest subset consisting of A 0s and B 1s from an array of strings
5Breaking an Integer to get Maximum Product

4. Unbounded Knapsack Problem

The Unbounded Knapsack problem can be defined as follows:

Given a knapsack weight W and a set of N items with certain value vi and weight wi, we need to calculate the maximum amount that could make up this quantity exactly. This is different from 0/1 Knapsack problem, here we are allowed to use an unlimited number of instances of an item.

Mathematically the problem can be expressed as:

Maximize [Tex]\sum_{i = 1}^{N}v_{i}x_{i}    [/Tex] subject to [Tex]\sum_{i = 1}^{N}w_{i}x_{i} \leq W    [/Tex] and [Tex]x_{i} \epsilon \mathbb{Z}    [/Tex] and xi ≥ 0.

Some practice problems on Unbounded Knapsack:

Sl. No.Problem
1Unbounded Fractional Knapsack
2Unbounded Knapsack (Repetition of items allowed)
3Unbounded Knapsack (Repetition of items allowed) | Set 2
4Find minimum number of coins that make a given value
5Coin Change

Variations of Knapsack Problem:

There are several variations possible for the Knapsack Problem. Some of the well-known variations are provided below:

1. Multi-objective Knapsack problem:

In this variation, the goal of filling the knapsack changes. Instead of maximizing only the value, there can be several other objectives.

For example: Consider you are organizing a music show in a hall that has a capacity of 10,000. You are organizing a show and the size of the audience depends on the popularity of the singers. Also, the more popular the singer is, the more the fee. You want to maximize the profit and minimize the amount spend on the singer simultaneously and also want to bring as many singers as possible.

2. Multi-dimensional Knapsack problem:

In this variation of the problem, the weight of any item i is given by an M dimensional vector {wi1, wi2, . . . wiM} and similarly, the capacity of the knapsack is also an M dimensional vector {W1, W2, . . . , WM}.

3. Multiple Knapsack problem:

This variation of the knapsack problem is similar to the Bin Packing algorithm. The difference in both the problem is here we can pick a subset of the items whereas, in the Bin Packing problem, we have to pack all the items in any of the bins. The idea is that there are multiple knapsacks which may seem like adding capacity to the initial knapsack, but it is not similar to that at all.

4. Quadratic Knapsack problem:

This variation has the goal of achieving the maximum value of a quadratic objective function that is subjected to binary and linear capacity constraints.

5. Geometric Knapsack problem:

In this variation, there is a set of rectangles with different values and a rectangular knapsack. The goal is to pack the largest possible value into the knapsack.

Applications of the Knapsack Problem:

The Knapsack problem has several real-life applications. Some of them are mentioned here:

  • One of the early applications of the Knapsack problem was in construction and scoring of exams in which the test takers have a choice as to which questions they answer.
  • The subset sum problem is solved using the concept of the Knapsack problem.
  • The multiple objective variations of the Knapsack problem is frequently used for transportation logistics optimization problems.
  • The multiple knapsack problem is often used in many loading and scheduling algorithms in Operational Research.

 


Reffered: https://www.geeksforgeeks.org

Algorithms

Related
10 Most Important Algorithms For Coding Interviews 10 Most Important Algorithms For Coding Interviews
Difference between Greedy Algorithm and Divide and Conquer Algorithm Difference between Greedy Algorithm and Divide and Conquer Algorithm
Transform and Conquer Technique Transform and Conquer Technique
Must Do Coding Questions for Product Based Companies Must Do Coding Questions for Product Based Companies
Maximum possible difference between two Subarrays after removing N elements from Array Maximum possible difference between two Subarrays after removing N elements from Array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 10



 

Horje