Posts match “ greedy-algorithm ” tag:

## [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 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.
1. Quick to design and implement the algorithm.
2. It can be very fast to model the problem.
• Problems:
1. No quality guarantees (in general). You don't know much you can improve the algorithm, you don't know how good they are.
2. 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

1. Describe the problem
2. Choose some decision variables
3. Express the problem constraints in term of there variables
4. Express the objective function ( the quality of the solution )
5. There may be many ways to model an optimization problem.

#### Modeling the knapsack problem

1. Describe the problem:
• For each i in Item, has weight Wi and value Vi.
• 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.
2. Choose some decision variables:
• Xi is item i is selected or not
3. Express the problem constraints in term of there variables:
4. Express the objective function ( the quality of the solution ) is maximum and be subject to
5. 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 capacity K of Item[ 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.