Knapsack Problem

One of the most popular decision-making problems. Many real-world applications can be modeled as a knapsack problem. What will you put into your knapsack (bag) so that the sum of product values are maximized? Combinations are

2^n

and it is hard constraint.

Knapsack Problems

Bin packing problem

binary knapsack problem

integer knapsack problem

Problem Modeling

Maximize

\sum_iv_ix_i

subject to

\sum_iw_ix_i < W

where

x_i\in\{0,1\} (i\in I)

and

$W$ - knapsack capacity limit

$v_i, w_i$ weight of product $i$

$x_i = 1$ means we choose product $i$

$N$ - number of items

Dynamic Programming

V[i, w] represents the optimal solution of a subproblem for products

1

i

and the maximum weight of

w

Given

N

products and weight

W, V[N,W]

is the solution

O(NW)

Pseudo polynomial complexity. Each product creates linear time complexity

Knapsack problem

The knapsack problem is the following problem in combinatorial optimization:Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

https://en.wikipedia.org/wiki/Knapsack_problem

algorithmsandme.com

https://algorithmsandme.com/dynamic-programming-0-1-knapsack-problem/

Knapsack Problem

Problem Modeling

Dynamic Programming

Recommendations