c语言背包问题_背包问题 贪心算法_c语言背包问题csdn(6)

经过两次转化，可以构造子结构了。用Max[y-1][i][j][k]表示在y-1行时，三条路线分别在i、j、k时所能取得的最大苹果数，用Max[y-1][i][j][k]可以求解任意的Max[y][i'][j'][k']，其中i' = i to j' , j' = j to k', k' = k to M. 如果线路重叠，苹果已经被取走，不用重复考虑。因此处理每一行时为了简单起见最好维护一个该位置苹果是否被取走的标志位，方便在路线重叠时计算。根据上面的范围关系，先求k'的所有情况，然后是j'，最后才是i'。这样Max[N][M][M][M]就是三趟后所能取得的最多苹果数。

参考资料

《算法导论》第15章动态规划、第16章贪心算法

《算法设计手册》第八章动态规划

《编程珠玑》相关问题

《编程之美》相关问题

poj 2411 & 编程之美 4.2 瓷砖覆盖地板

最大连续子序列乘积

Dynamic Programming: From novice to advanced

双调欧几里德旅行商问题（算法导论思考题15-1）

评：网络上的很多中文版本，都不如直接看这篇文章里的英文原版解答理解的清楚。

整齐打印（算法导论思考题15-4）

评：难度不高，注意要求的是空格数的立方和最小。

动态规划应用：Viterbi算法

评：需要一些马尔科夫链的知识。理解起来不是很容易，理解以后是不是有种像是更多个生产线的装备线调度？

最高效益的调度（算法导论思考题15-7）

评：和0-1背包问题何其相似。

8-24.

给定一个种类的集合，找出凑出给定一个值所用的最小数目。

解答：

正文问题1已做解答，略。

8-25.

长度为n的数组，其中元素可正可负可零。找出数组索引i,j使得从i到j的元素之和最大。

解答：

最大连续自序列和问题，请参考正文问题5的解答。

8-26.

假设你有一页纸，正面和背面都写满了字母，当剪掉正面上一个字母时，这一页的背面的字母也会被剪掉。设计一个算法来验证是否能通过这张纸生成一个给定的字符串？提供一个函数，当你输入一个字母的位置时能够返回它背面的字母。（叙述关键思路即可）

解答：

目前我所看到的最容易理解的解法是使用最大流来解的：

下面把思路大意翻译一下。

假设需要拼成的字符串是"FOO"，同时这张纸的正反面对应位置上的内容（可以通过提供的函数获得）分别是：

由于位置4上的字母的正反面都用不到，忽略。

把这个表格转化成一个两层结点的流量网络

其中源点下面第一层表示拼成所需字符串的所有字母，源点到达该点的流量是需要的数目。第一层与第二层相连接表示某一位置上对应的是哪个所需字母，比如位置1正反面分别是F和O，表示它能提供1个F的入度和1个O的入度，但又由于一个片纸无论正反面只能用一次，那么它只能提供1的出度，直接连接汇点。

这个问题是否有解，等价于这个流量网络中是否存在一个流使得源点的流的出度等于汇点流的的入度，即一个最大流问题。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23984-6.html