Seonglae ChoOne 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 and it is hard constraint.
Knapsack Problems
Problem Modeling
Maximize subject to where and
- - knapsack capacity limit
- weight of product
- means we choose product
- - number of items
Dynamic Programming
V[i, w] represents the optimal solution of a subproblem for products
to and the maximum weight of
Given products and weight is the solution
- Pseudo polynomial complexity. Each product creates linear time complexity