[Discrete Optimization Note] 2. Knapsack problem
This is my note for Discrete Optimization in Coursera (https://class.coursera.org/optimization002)
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 subproblemO( k, j  1 )
first.