学完01背包后，再来学习这份文档

Let’s Remember DP

  • We need to do maximization/minimization on certain problem (e.g. KnapSack Problem).
  • We formulate State, each State S_Root, has SubStates S_child1, S_child2, S_child3
  • Each _S_child _is another state, has sub states
  • We don’t know the OPTIMAL, we try EVERY child and optimize based on that

Greedy

  • Do only 1 choice (The Greedy Choice) based on Intuition/Heuristic(直觉/启发)
  • Then we move to only ONE child substate, only new subproblem, and again apply the Greedy Choice
  • Greedy finds a global optimum solution or approximate solution
  • In contests, we only care with global optimum solution problems
  • In real life, both types are critical, and approximate type is more important

More

  • A greedy algorithm always makes the choice that looks “best at the moment”
  • That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution
  • You must have proof, in case globally optimal solution greedy Algorithms
  • In competitions, most of time, we find strong Intuition and don’t proof it. Use examples to challenge your idea.
  • After competitions, think WHY that was correct. Ignoring this will make you weak contestant
  • Study proofing techniques so that you are able to formulate a mathmatical proof
  • Sometimes greedy and dp exist for same problem, many times, greedy only is feasible

Example 1: Activity selection problem

  • Given a set of activities, each one has: Start time S[i] and finish time F[i]
  • Find the maximum number of activities that don’t overlap
  • Activity can start directly when an activity ends. E.g. activity(10, 15) could start after activity (7, 10)

DP solution

  • The problem could be formualted as DP easily, it is subset style one. We finally has 01001011101 space
  • But, how to manage? if we picked an activity, what to call? some activities before & after me are fine!!
  • Sort the activities so that we look one way. Sort based on activities Start or Finish times
  • One restriction, when we pick one, we should call on the first activity one that don’t overlap, NOT the direct next one.
  • So each state has 2 choices: Pick or Leave
  • Could we find a way such that, each time, we decide Pick or Leave? If so, you found Greedy solution

Greedy

  • Let’s try some Intuitions.
  • What about: Let’s count for each activity, how many ones that intersect with you? Then sort based on the minimum intersections?
  • Wrong! See the image as an example to fail.
  • What about doing a selection that would leave as many of the activities as possible.
  • If activites are sorted based on start time, picking first one don’t do so
  • Example: Imagine first activity has smallest start time and biggest end time. Picking it will discard all others!
  • What If activites are sorted based on finish time? Make sense!
  • The first ending activity, discard all overlapping with it, but give space for all next activities!
  • Time for a proof! So that we are sure from this intuition!
  • Let S = {1, 2, . . ., n} be the set of activities ordered by finish time. Thus activity 1 has the earliest finish time.
  • Suppose, A is a subset of S is an optimal solution and let activities in A be ordered by finish time. Suppose, the first activity in A is k.
  • If k = 1, then A begins with greedy choice and we are done (or to be very precise, there is nothing to prove here).
  • If k not=1, we want to show that there is another solution B that begins with greedy choice, activity 1.
  • Let B = (A - {k}) U {1}. Because f[1] =< f[k], the activities in B are disjoint
  • Since B has same number of activities as A, i.e., |A| = |B|, B is also optimal.

Example 2: Fractional Knapsack Problem

Given a knapsack with capacity R and materials of different values per unit volume, find the most valuable combination of materials

which fit in a knapsack of fixed volume R. We are allowed to take “fractions” of materials.
E.g. Say we have 20 Kilo Rice With Total Money 60 and 5 Kilo Cheese With Total Money 50
If we have knapsack of 7 Kilos: Optimal solution will be: Pick 5 Kilo Cheese and 2 Kilo Rice with money benfit: 50 + 2 * 20/60

DP solution
Very similr to old one (actually like coin change code), we pick 1 kilo and try to pick another.

Greedy
Q: If you have R=1, what could you do?
I will pick it from item with heighst price? No
I will pick it from item with heighst price PER kilo
E.g. In this case, 1 Kilo from cheese is 50/5 Pounds.
What if 2 kilos? Again, pick next one from from Rice and so on..till highest per kilo finish!
We got a solution! Sort items based on ratio Money / Weight. Pick from items in order.
As long as item has more kilos, take from it, else move to next item!

O(nlogn) solution: sort + process Although idea is simple! Proof is about 1 complete page!