Introduction to 0/1 Knapsack

Overview

A knapsack is defined as a bag carried by hikers or soldiers for carrying food, clothes, and other belongings. The Knapsack problem, as the name suggests, is the problem faced by a person who has a knapsack with a limited capacity and wants to carry the most valuable items. In other words, we are given $N$ items, each having a specific weight and a value, and a knapsack with a maximum capacity. Our job is to put as many items as possible in the knapsack such that the cumulative weight of the items doesn't exceed the knapsack's capacity, and the cumulative value of the items in the knapsack is maximized.

In this pattern, we will be discussing 8 problems related to this pattern. The following diagram shows an overview of this pattern.

The 0/1 Knapsack is a special case of the Knapsack problem where item selection has some constraints. In general, the following restrictions are applied:

• A maximum of one item can be selected of each kind, that is, the number of items of each kind in the knapsack is either zero or one.

• We can't take a fraction of an item, that is, we either have to take the complete item or leave it.

Mathematically, Given a set of $n$ items, each with a value $v_i$ and weight $w_i$ , and a knapsack with maximum weight capacity $C$ , we have the following target:

• maximize $\sum_{i=1}^n x_iv_i$

• subject to $\sum_{i=1}^n x_i w_i \leq C$

  • with $x_i \in \{0, 1\}$ representing the number of instances of item $i$ in the knapsack.

Examples

Does my problem match this pattern?

• Yes, if the problem exhibits both of these characteristics:

  • Selection, that is, we need to select some items from a pool of items where each item has a specific value. Furthermore, a maximum of one item can be selected of each kind.

  • Maximum capacity, that is, the total cost of the above-mentioned selection can't exceed a specified target. This cost can be weight, distance, price, or any other material value.

• No, if any one of these conditions is fulfilled:

  • Multiple items or a fraction of an item can be selected of each kind.

  • There's no bound on the capacity of the target.

Real-world problems

There are many problems related to selection, allocation, optimization, and scheduling that can be solved using the 0/1 knapsack pattern. A couple of real-world scenarios are discussed below:

• Resource allocation: Allocate a number of people with varying wages and productivity to perform a task so that it's done within the allocated time.

• Machine scheduling: Schedule a number of jobs with different processing times and value addition on a machine so that the overall throughput is maximized.

Strategy time!

Match the problems that can be solved using the 0/1 knapsack pattern.

Note: Select a problem in the left-hand column by clicking on it, and then click on one of the two options in the right-hand column.