Algorithm代写：CS406 Greed Algorithm

发表于   |   分类于

Introduction

Greedy Algorithm，也就是贪心算法，局部最优化的算法，虽然可以快速得到解，但是这个解往往不会是全局最优解。不过这个算法的思想倒是挺有趣的。

Requirement

Consider the following solitaire game: you are given a list of moves, x1, x2…xm, and their costs, y1, y2…ym. Moves and their costs both take the form of positive integers. Such a list of moves and their costs is called an instance of the game. To play the game, you start with a positive integer n. On each turn of the game you have two choices: subtract 1 from n incurring a cost of 1 or pick some move xi such that n is divisible by xi and divide n by xi incurring a cost of yi. The goal is to get to 0 while incurring the minimum possible cost.
For instance, suppose that the set of moves is 4, 5, 7 and the corresponding penalties are 1, 3, 4. If n is 20 then the optimal strategy is as follows:

  1. Divide 20 by 4 to get 5, incurring a cost of 1
  2. Subtract 1 from 5 to get 4 incurring a cost of 1
  3. Divide 4 by 4 to get 1, incurring a cost of 1
  4. Subtract 1 from 1 to get 0, incurring a cost of 1

So the final cost is 4. One suboptimal strategy for this game is as follows:

  1. Divide 20 by 5 to get 4, incurring a cost of 3
  2. Divide 4 by 4 to get 1, incurring a cost of 1
  3. Subtract 1 from 1 to get 0, incurring a cost of 1

which gives us a total cost of 5.
One possible greedy algorithm for this game is as follows: On each turn, simply divide the current number by the legal move x of cost y which maximizes x / y - the ratio of move to cost (and subtract 1 from the current number if it is not divisible by any move). If two legal moves have the same ratio of move to cost then the greedy algorithm will take the larger move. Unfortunately, this greedy algorithm does not always give the optimal strategy. In this problem you will find counterexamples that show the greedy algorithm is not optimal in different instances of this game.

Tips:

  • To find instances where the greedy algorithm fails, you will probably need to be able to find the optimal strategy in all instances. What kind of algorithm can you use to do this?
  • Most of the difficulty of this assignment is in coming up with the right approach. The code you write does not need to be especially long or complex to solve the problem.
  • It may take some time for your code to find a counterexample, particularly for the last couple instances. But if it takes more than a couple of minutes, you probably need to rethink your approach.
  • When searching for instances of where the greedy algorithm fails, it is useful to avoid redoing work.
  • For reference, the optimal cost for the instance (3, 1), (2, 1) when n is 321 is 10, and the greedy algorithm gives 11. The smallest value of n for which the greedy algorithm fails on the instance (211, 2), (210, 1) is 4740960.
  • Start early. You have two weeks to do this problem, so you shouldn’t try to do it all in the last day.