Learn and practice the Greedy Techniques and Dynamic Programming patterns to solve coding interview problems.

Educative-99 in Python: Accelerate Your Coding Interview Prep

This module teaches you two of the most important problem-solving techniques in the optimization domain: Greedy Techniques and Dynamic Programming. Not all problems require an exhaustive search through the solution space. Rather, consistently choosing the locally optimal solution can be proven to yield the globally optimal solution. In such situations, Greedy Techniques result in simple, highly efficient solutions. Other problems have a well-defined structure, where the same subproblem is encountered and solved multiple times. Dynamic Programming techniques allow us to compute once and reuse the solutions to recurring subproblems.

Optimization Techniques

# Statement

You are given $n$ items whose weights and values are known, as well as a knapsack to carry these items. The knapsack cannot carry more than a certain maximum weight, known as its **capacity**.

You need to maximize the total value of the items in your knapsack, while ensuring that the sum of the weights of the selected items does not exceed the capacity of the knapsack.

If there is no combination of weights whose sum is within the capacity constraint, return $0$.

>**Notes:** 
> 1. An item may not be broken up to fit into the knapsack, i.e., an item either goes into the knapsack in its entirety or not at all. 
> 2. We may not add an item more than once to the knapsack. 

**Constraints:**

* $1 \leq$ `capacity` $\leq 1000$
* $1 \leq$ `values.length` $\leq 500$
* `weights.length` $==$ `values.length` 
* $1 \leq$ `values[i]` $\leq 1000$
* $1 \leq$ `weights[i]` $\leq$ `capacity`

# Examples

0/1 Knapsack

Statement