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
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
