Skip to content

Latest commit

 

History

History
24 lines (16 loc) · 634 Bytes

README.md

File metadata and controls

24 lines (16 loc) · 634 Bytes

Binary Knapsack Problem Dynamic Programming

It is a classic dynamic programming problem in which we have to collect items in the knapsack in such a way that our profit is maximized. The difference between this problem and the fractional knapsack one is that you CANNOT take a fraction of an item.

Approach

The algorithm to solve the problem has been implemented in three ways:

  • recursive
  • top-down
  • bottom-up (Dynamic Programming)

Time Complexity

The time complexity of the dynamic programming solution is: O(N^2)

Directory Structure

📦Binary-Knapsack-Problem-DP
┣ 📜main.cpp
┗ 📜README.md