算法（三）--------扔鸡蛋问题和找零钱问题

 

扔鸡蛋问题描述：You are given two eggs, and access to a 100-storey building. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor.

What strategy should you adopt to minimize the number of egg drops it takes to find the solution?

找零钱问题描述：

• 当硬币系统为2角5分、 1角、 5分、 1分时，要找给顾客6角3分钱，怎么做？所拿出的硬币个数最少
　　– 最优解： 6角3分 = 2个2角5分 + 1个1角 + 3个1分，最优值为6 coins
　　– 阶段：每次…
• 状态（子问题的规模）：剩余数额
• 决策：每次在2角5分、 1角、 5分、 1分中选择一个面值不超过剩余数额的最大硬币
• 当硬币系统为4分、 3分、 1分时，要找给顾客6分钱，怎么做？
　　– 依照上述策略， 6分 = 1个4分 + 2个1分， 3 coins
　　– 而2个3分才是最优解！

解决方案：

•选择组成6¢的硬币的最少数目 (1¢, 3¢, and 4¢)

选取所以的硬币1¢, 2¢, 3¢, ..., 6¢
组成 1¢, 仅仅使用 1¢ 就可以 (1 coin)
组成 2¢, 使用1¢+1¢ (1 coin + 1 coin = 2 coins)
组成 3¢, 使用3¢ coin (1 coin)
组成 4¢, 使用4¢ coin (1 coin)
组成 5¢, try
1¢ + 4¢ (1 coin + 1 coin = 2 coins)
2¢ + 3¢ (2 coins + 1 coin = 3 coins)
原问题：组成 6¢, try
1¢ + 5¢ (1 coin + 2 coins = 3 coins)
2¢ + 4¢ (2 coins + 1 coin = 3 coins)
3¢ + 3¢ (1 coin + 1 coin = 2 coins)      ------>最好的方案