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

解法：

尽管可以通过递归计算取1<=k<n使得P(n)=∑P(k)P(n-k)，遍历所有P(n)种方案，但这并不是一个高效率的解法。

经过以上几道题的锻炼，很容易看出，子结构是求Ai...Aj的加括号方法m[i][j]可递归地定义为

\[m[i][j]=\left\{\begin{matrix} 0& if \ i=j\\ \underset{i\leqslant k<j}{min}\begin{Bmatrix} m[i][k] + & m[k+1][j] +& p_{i-1}p_{k}p_{j} \end{Bmatrix} & if \ i<j \end{matrix}\right.\]

这样，只需利用子结构求解m[1][n]即可，并在在构造m[1][n]的同时，记录状态转换。下面的代码展示了这个过程，不再仔细分析。

扩展：

矩阵链乘法的备忘录解法（伪码），来自《算法导论》第15章。

难度评级：★★

一个贼在偷窃一家商店时发现了n件物品，其中第i件值vi元，重wi磅。他希望偷走的东西总和越值钱越好，但是他的背包只能放下W磅。请求解如何放能偷走最大价值的物品，这里vi、wi、W都是整数。

解法：

如果每个物品都允许切割并只带走其一部分，则演变为部分背包问题，可以用贪心法求解。0-1背包问题经常作为贪心法不可解决的实例（可通过举反例来理解），但可以通过动态规划求解。c语言背包问题

为了找出子结构的形式，粗略地分析发现，对前k件物品形成最优解时，需要决策第k+1件是否要装入背包。但是此时剩余容量未知，不能做出决策。因此把剩余容量也考虑进来，形成的状态由已决策的物品数目和剩余容量两者构成。这样，所有状态可以放入一个n*(W+1)的矩阵c中，其值为当前包中物品总价值，这时有

\[c[i][j]=\left\{\begin{matrix} c[i-1][j]& if \ w_{i}>j\\ \max\begin{Bmatrix} c[i-1][j-w_{i}]+v_{i} \ ,\ c[i-1][j] \end{Bmatrix} & if \ w_{i}\leqslant j \end{matrix}\right.\]

根据这个递推公式，很容易写出求解代码。

难度评级：★★★

无向图G中有N个顶点，并通过一些边相连接，边的权值均为正数。初始时你身上有M元，当走过i点时，需要支付S(i)元，如果支付不起表示不能通过。请找出顶点1到顶点N的最短路径。如果不存在则返回一个特殊值，如果存在多条则返回最廉价的一条。限制条件：1<N<=100; 0<=M<=100 ; 对任意i, 0<=S[i]<=100。

解法：

如果不考虑经过顶点时的花费，这就简化成了一个一般的两点间最短路径问题，可以用Dijkstra算法求解。加入了花费限制之后，就不能直接求解了。

考察从顶点0到达顶点i的不同状态，会发现它们之间的区别是：总花费相同但路径长度不同、总花费不同但路径长度不同。为了寻找最短路径，必然要保存到达i点的最短路径；同时为了找到最小开销，应该把到达i点的开销也进行保存。根据题目的数值限制，可以将总开销作为到达顶点i的一个状态区分。这样，就可以把Min[i][j]表示为到达顶点i（并经过付钱）时还剩余j元钱的最短路径的长度。在此基础上修改Dijkstra算法，使其能够保存到达同一点不同花费时的最短长度，最终的Min[N-1][0...M]中最小的即为所求。以下是求解过程的伪代码。

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