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

难度评级：★★★

用 1 * 2 的瓷砖覆盖 n * m 的地板，问共有多少种覆盖方式？

解法：

（启发来自于：poj 2411 & 编程之美 4.2 瓷砖覆盖地板，下文叙述做了点修改）

分析子结构，按行铺瓷砖。一块1*2瓷砖，横着放对下一行的状态没有影响；竖着放时，下一行的对应一格就会被占用。因此，考虑第i行的铺法时只需考虑由第i-1行造成的条件限制。枚举枚举第i-1行状态即可获得i行可能的状态，这里为了与链接一文一致，第i-1行的某格只有两个状态：空或者放置。空表示第i行对应位置需要放置一个竖着的瓷砖，这时在铺第i行时，除去限制以外，只需考虑放还是不放横着的瓷砖这2种情况即可（不必分为放还是不放、横到下一层还是竖着一共4种）。同时对于第i-1行的放法，用二进制中0和1表示有无瓷砖，那么按位取反恰好就是第i行的限制条件。

难度评级：★★

假设书架上一共有9本书，每本书各有一定的页数，分配3个人来进行阅读。为了便于管理，分配时，各书要求保持连续，比如第1、2、3本书分配给第1人，4、5分配给第二人，6，7，8，9分配给第3人，但不能1，4，2分配给第1人，3，5，6分配给第2人。即用两个隔板插入8个空隙中将9本书分成3部分，书不能换位。同时，分配时必须整本分配，同一本书不能拆成两部分分给两个人。为了公平起见，需要将工作量最大的那一部分最小化，请设计分配方案。用s1,...,sn表示各本书的页数。

解法：

继续从子结构的角度出发，发现如果前面的k-1份已经分好了，那么第k份自然也就分好了。用M[n][k]表示将n本书分成k份时最小化的k份中的最大工作量，从第k份也就是最后一份的角度来看，总数-它的不同情况下数量 = 前k-1份的数量和。

\[M[n][k] = \overset{n}{\underset{i=1}{min}}\max(M[i][k-1],\sum_{j=i+1}^{n}s_{j})\]

除此以外，初始化为

\[M[1][k] = s_{1},for \ all \ k>0\\ M[n][1] = \sum_{i=1}^{n}s_{1}\]

自底向上地可以求得使M[n][k]最小化的解。

其他：

这个问题被称为线性分割(linear partition)问题，有不少的应用情形。如，一系列任务分配给几个并行进程，那么分配工作量最大任务的那个进程将成为影响最终完成时间的瓶颈。将最大的工作量尽量减少，能够使所有工作更快地完成。

难度评级：★★★

（问题1的相关问题(1)的进一步扩展）一个矩形区域被划分为N*M个小矩形格子，在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，每经过一个格子就把其中的苹果全部拿走，最后到达(N,M)。此时，只允许向上或向左走一步，反方向走回(1,1)。这一趟可以不走第一趟的路线，但当经过第一趟所经过的格子时，里面已经没有苹果了。到达(1,1)后，再次反方向地只允许向右或向下走，走到(N,M)，同样可以不走前两趟走过的路线。求这三趟的走法，使得最终能拿取最多数量的苹果。

解法：

这个问题有两个难点，首先要理清三条路线的关系。可以发现，虽然第二趟方向相反，但其实和从(1,1)走到(N,M)是一样的，即三趟路线全部可以转化为从(1,1)向下或向右走到(N,M)的过程。

观察三条路线可以发现，实际中走的时候如果路线有交叉，可以把这种情况转化为相遇而不交错的情况如下图：

这样做的好处是，对于红线和蓝线上同一行j的点的坐标(i,j)(i',j)，总有i<=i',这样就能够把三条路线划分成左、中、右三条有序的路线。

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