Day-17: 0/1 Knapsack Problem

Day-17: 0/1 Knapsack Problem

0/1 Knapsack problem is one of the most popular optimization problems out there.

The problem considers a knapsack and n items that have different weights and different values.

The knapsack can hold elements whose total makes M kg or less.

Dynamic programming helps us find the biggest value that can be reached.

Time complexity: O(nm) (In an iterative solution, the complexity can be reduced to linear time by just storing last two rows)

Here is the link of my C++ implementation of Knapsack: 0/1 Knapsack

Author face

Abdurrezzak Efe

Bilkent University Bachelor's in CS 2018'

Recent post