扔鸡蛋问题和找零钱问题

算法(三)--------扔鸡蛋问题和找零钱问题

 

扔鸡蛋问题描述: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)      ------>最好的方案

上一篇:Leetcode solution 322: Coin Change


下一篇:【LeetCode】322. Coin Change