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

动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一，并不像回溯法具有解决绝大多数问题的银弹（全面解析回溯法：算法框架与问题求解)。为了解决动态规划问题，只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集，希望能有所帮助。难度评级受个人主观影响较大，仅供参考。

目录（点击跳转）

动态规划求解的一般思路：

判断问题的子结构（也可看作状态），当具有最优子结构时，动态规划可能适用。

求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。分治法则不同，每次递归都产生新的问题。

重新构造一个最优解。

备忘录法：

动态规划的一种变形，使用自顶向下的策略，更像递归算法。

初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。

实例可以参照矩阵链乘法部分。

难度评级：★

假设有几种，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的数。

解法：

用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小数。对于不同的面值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数目的找零total，需要求解sum[total]的值。

通过sum[total].lastSum和sum[total].addCoin，很容易通过循环逆序地或者编写递归调用的函数正序地输出从结束状态到开始状态使用的种类。以下各题输出状态转换的方法同样，不再赘述。下面为了方便起见，有的题没有在构造子结构的解时记录状态转换，如果需要请类似地完成。

扩展：

(1)一个矩形区域被划分为N*M个小矩形格子，在格子(i,j)中有A[i][j]个苹果。c语言背包问题现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，最后到达(N,M)，每经过一个格子就把其中的苹果全部拿走。请找出能拿到最多苹果数的路线。

难度评级：★

分析：

求解程序略。

(2)装配线调度（《算法导论》15.1）

难度评级：★

难度评级：★

对于序列S和T，它们之间距离定义为：对二者其一进行几次以下的操作(1)删去一个字符；(2)插入一个字符；(3)改变一个字符。每进行一次操作，计数增加1。将S和T变为同一个字符串的最小计数即为它们的距离。给出相应算法。

解法：

将S和T的长度分别记为len(S)和len(T)，并把S和T的距离记为m[len(S)][len(T)]，有以下几种情况：

如果末尾字符相同，那么m[len(S)][len(T)]=m[len(S)-1][len(T)-1]；

如果末尾字符不同，有以下处理方式

修改S或T末尾字符使其与另一个一致来完成，m[len(S)][len(T)]=m[len(S)-1][len(T)-1]+1；

在S末尾插入T末尾的字符，比较S[1...len(S)]和S[1...len(T)-1]；

在T末尾插入S末尾的字符，比较S[1...len(S)-1]和S[1...len(T)]；

删除S末尾的字符，比较S[1...len(S)-1]和S[1...len(T)]；

删除T末尾的字符，比较S[1...len(S)]和S[1...len(T)-1]；

总结为，对于i>0,j>0的状态(i,j),m[i][j] = min( m[i-1][j-1]+(s[i]==s[j])?0:1 , m[i-1][j]+1, m[i][j-1] +1)。

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