如果累了的话,不妨看一下超可爱的漫画吖
来源:伯乐专栏作者/玻璃猫,微信公众号 - 梦见
主页君小提示:图文有点长,慢慢看,
做好防查颓措施
问题
现在有$10$级台阶,要求从第一阶向上走,每一次可以走一步或走两步,求有多少种不同走法。
比如说我们可以一阶一阶的走,一共走10步。这是一种走法。
就像这样:
当然啦,除此之外,还有很多种走法……
第一种情况
第二种情况
$F(0) = 0;$
$F(1) = 1;$
$F(2) = 2;$
$F(i) = F(i - 1) + F(i - 2)$
int work(int i){ |
int work(int i){ |
问题
有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。
参与挖矿工人的总数是10人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。
要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?
每一座金矿都有挖与不挖两种选择,如果有N座金矿,排列组合起来就有2^N种选择。
对所有可能性做遍历,排除那些使用工人数超过10的选择,在剩下的选择里找出获得金币数最多的选择。
代码比较简单就不展示了,时间复杂度也很明显,就是O(2^N)。
F(n,w) = 0 (n<=1, w < p[0]);
F(n,w) = g[0] (n==1, w >= p[0]);
F(n,w) = F(n-1,w) (n>1, w < p[n-1])
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w >= p[n-1])