KeenTween
  • Home
  • Inspire her
  • Phenom
  • STEM
  • Gender
  • FUN
  • summer fun
  • Then & Now
  • Empathy
  • About

Knapsack  problems  are All Around Us


'The Knapsack Problem' is a classic problem in computer science - You have a knapsack and several items to pack into it. Each item has a weight and a value, and you can only carry up to a maximum weight. Find a combination of items to pack, such that you remain under the weight limit, but you maximize the value of the items selected.

1. explanation of the Knapsack Problem


2. the knapsack problem


3. p vs np


Stephen Cook and Leonid Levin formulated the P (easy to find) versus NP (easy to check) problem independently in 1971.


While seemingly straightforward, this problem requires a surprising amount of thought to solve! In this video, we look at the naive recursive solution first, before moving on to a far more efficient dynamic programming solution!

While seemingly straightforward, this problem requires a surprising amount of thought to solve! In this video, we look at the naive recursive solution first, before moving on to a far more efficient dynamic programming solution! The idea of recursion is not very common in real world. So, it seems a bit confusing to the novice programmers.

what recursion is about:

* It is a mathematical function.
* That calls itself to compute a value corresponding to an n-th element..
which defines some boundaries. Recursion is when a function can call itself.

If you understand namespaces and scope and how parameters are passed to a function, then you know recursion already.
 

In operations research, applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not tractable.

It operates on the domain of those optimization problems in which the set of feasible solutions is discrete or can be reduced to discrete.

In which the goal is to find the best solution. Some common problems involving combinatorial optimization are the travelling salesman problem (TSP), the minimum spanning tree problem (MST), and the knapsack problem.




Science

Technology

Engineering

Mathematics

Empowerment

  • Home
  • Inspire her
  • Phenom
  • STEM
  • Gender
  • FUN
  • summer fun
  • Then & Now
  • Empathy
  • About