[Discrete Optimization Note] 2. Knapsack problem
This is my note for Discrete Optimization in Coursera (https://class.coursera.org/optimization-002)
Greedy Algorithm Intuition
What is Greedy? Build a solution by picking itmes one at a time in greedy fasion.
Idea 1: more items are best.
Start with small ones and take as many as you can.
Idea 2: valuable items are best.
Start with the most valuable items.
Idea 3: value density!
Calculate dollars per kilogram.
Greedy Algorithm
- For one problem, there are many possible greddy algorithms. Some will do better than others. (Take a look at above ideas)
- Idea: Take the most valuable items first. And the next valuable item that can fit into a knapsack.
- Advantages:
- Quick to design and implement the algorithm.
- It can be very fast to model the problem.
- Problems:
- No quality guarantees (in general). You don't know much you can improve the algorithm, you don't know how good they are.
- Quality can vary widely on the input.
Summary of Greedy Algorithm:
Try to understand what the problem is. Get a base line, that's what you have to improve and then afterwards you going to use some of the techniques that we will present:
- Constraint Programming
- Local Searching
- Mixed Integer Programming To improve the greedy algorithm and find out how much you can improve.
Modeling
How to formalize an optimization task as a mathematical model. This is the key to solve the optimal problem.
How to model an optimization problem
- Describe the problem
- Choose some decision variables
- Express the problem constraints in term of there variables
- Express the objective function ( the quality of the solution )
- There may be many ways to model an optimization problem.
Modeling the knapsack problem
- Describe the problem:
- For each
i
inItem
, has weightWi
and valueVi
. - We have a knapsack which capacity is
K
. - We have to find the subset of
Item
which value is maximum and summation of weight is less than or equal to K.
- For each
- Choose some decision variables:
-
Xi
is itemi
is selected or not
-
- Express the problem constraints in term of there variables:
- Express the objective function ( the quality of the solution ) is maximum and be subject to
- There may be many ways to model an optimization problem.
Dynamic Programming
Basic Principle:
- divide and conquer
- bottom up computation
Define the problem:
- Item selection
I = { 1, 2, 3 ...... n }
-
O( k, j )
is the optimal solution of capacityK
ofItem[ 1 ... j ]
s.t.
maximize
and subject to
Recurrence relation
- Before we want to solve
O( k, j )
, we solve sub-problemO( k, j - 1 )
first.O( k, j ) = max( O( k, j - 1 ), O( k - Wj, j - 1 ) + Vj ) if Wj <= K // 第一個是不拿j, 第二個是拿j O( k, j ) = O( k, j - 1 ) if Wj > K // 超重不拿j O( k, 0 ) = 0 // 什麼都不拿,價值就為零。