## Knapsack Algorithm

Hi, It is my first blog post about Knapsack Algorithm.

### Letβs Start

What is it? The Knapsack Algorithm (Knap) is piece of Cambinatoric and Dynamic Programming.

Firstly, let me explain about knapsack, the main problem of Knapsack is, given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

May be you have question,how is it related to combinatoric, so the answer is, we should generate all items that we can put in our Knap, that total weight of this items will not reach the max weigth of KNAP, but If we will do it with brute force (stupid code) the complexcity will very big. (I think, This part is clear π)

However, we can use dynamic programming, that optimize our stupid code. How we will do it.

Look on this imageπππ We will write same algorithm like this table.

PseudoCodeπππ

So you can check yourself in this problem. The problem is a little bit π different π, but you can found using logic π (Hint: can use one item many times)) Good Luck!!!