A checkerboard has a certain number of coins on it
A robot starts in the upper-left corner, and walks to the bottom left-hand corner
The robot can only move in two directions: right and down
The robot collects coins as it goes
You want to collect all the coins using the minimum number of robots
Example:
Do you see a greedy algorithm for doing this?
Does the algorithm guarantee an optimal solution?
Can you prove it?
Can you find a counterexample?
简单的说：
机器人从如图所示的位置出发，值能向右和向下行走，不能后退和上走，问如何才能用最少的机器人捡完所有的硬币。N*N。所以需要一个N平方级别的时间复杂度。不能用递归算。
谁能给个好的算法，多谢了
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 算法理论与分析 』 → [求助]机器人拾硬币
(订阅本版)
2006/11/28 13:25:00
新浪微博
[求助]机器人拾硬币
