18-06-2013, 04:35 PM
Greedy vs Dynamic Programming Approach
Greedy vs Dynamic.ppt (Size: 155 KB / Downloads: 121)
INTRODUCTION
Greedy and Dynamic Programming are methods for solving optimization problems.
Greedy algorithms are usually more efficient than DP solutions.
However, often you need to use dynamic programming since the optimal solution cannot be guaranteed by a greedy algorithm.
DP provides efficient solutions for some problems for which a brute force approach would be very slow.
To use Dynamic Programming we need only show that the principle of optimality applies to the problem.
Variations of the Knapsack problem
Fractions are allowed. This applies to items such as:
bread, for which taking half a loaf makes sense
gold dust
No fractions.
0/1 (1 brown pants, 1 green shirt…)
Allows putting many items of same type in knapsack
5 pairs of socks
10 gold bricks
More than one knapsack, etc.
First 0/1 knapsack problem will be covered then the Fractional knapsack problem.
Approximation algorithms
Approximation algorithms attempt to evaluate how far away from the optimum OPT, are the solutions solAlg provided by an algorithm in the worst case
Many criteria are used. We use OPT/solAlg for maximization, and attempt to establish OPT/solAlg<=K where K is a constant (solAlg/OPT for minimization)
The following slides show that the “best” greedy algorithm for 0/1 knapsack, greedy 4 does not satisfy OPT/solAlg<=K
Often greedy4 gives an optimal solutions, but for some problem instances the ratio can become very large
A small modification of greedy4, however, guarantees, that OPT/alg<=2
This is a big improvement.
There are better approximation algorithms for knapsack
Principle of Optimality for 0/1 Knapsack problem
Theorem: 0/1 knapsack satisfies the principle of optimality
Proof: Assume that itemi is in the most beneficial subset that weighs at most W. If we remove itemi from the subset the remaining subset must be the most beneficial subset weighing at most W - wi of the n -1 remaining items after excluding itemi.
If the remaining subset after excluding itemi was not the most beneficial one weighing at most W - wi of the n -1 remaining items, we could find a better solution for this problem and improve the optimal solution. This is impossible.