-
What do you get if you follow the greedy algorithm? What's the first thing the thief does?
如果年贪婪算法你会带走什么呢？,这个贼做的第一件事是什么？
-
We'll start with the greedy thief. Well, the greedy thief follows the greedy algorithm.
我们从贪婪的贼开始,这个贪婪的贼按贪婪算法行动。
-
This light is probably on to keep burglars away and so: "stop," right?
这个灯很可能是为了防止夜贼入侵的？
-
There's no more room. So the greedy thief take that and leaves.
所以这个贪婪的贼就带着这些东西走了,但是这并不是一个最优选择。
-
Instead of taking that one vase, the thief could take two radios. And get more value. So the greedy thief, in some sense, gets the wrong answer. But maybe isn't so dumb.
这个贼可以带走两个收音机，这样总价值更大，因此这个贪婪的贼,在某种意义上没有得到正确的答案,但是可能它也不笨。
-
We're exhausting all possibilities. And then choosing the winner. Well, that's what the slow thief tried. Unfortunately it took so long that before he finished the owner returned home, called the police and the thief ended up in jail.
我们穷举了所有可能方案,然后选择最优方案,这就是动作慢的贼的方案,不幸的是它在失主回家之前，要花上了太长的时间。
-
But it's not an optimal solution.
这个贼应该做什么呢？
-
It happens. Fortunately, while sitting in jail awaiting trial, the slow thief decided to figure what was wrong. And, amazingly enough, he had studied mathematics. And had a blackboard in the cell. So he was able to work it out.
失主叫了警察然后小偷最后被抓进了监狱,幸运的是这个贼做来牢房里,等待判决时发现了自己的错误,它很惊人的学习过数学，牢房里,还有一个黑板，它可以把题目算出来了。
-
That gets us to the smart thief. Why is this thief smart? Because she took 600. And she learned 600 that in fact there is a good way to solve this problem. And that's what we're going to talk about next. And that's something called dynamic programming.
现在我们要当聪明的贼,这个贼为什么聪明呢？,因为它选择了,它知道这事实上是解决这个问题的好方法,这就是我们接下来要讲的,也就是动态编程。
应用推荐