算法设计方法4：动态规划经典例题总结( 四 ) _动态规划

< n; i++){for (j = i+1; j < n; j++){/*如果前面的值小于后面的值则调换位置*/if (ave[s[i]] <= ave[s[j]]){/*注意这里互换的是下标并不是真正的值，因为后面还要用到重量*/int temp = s[i];s[i] = s[j];s[j] = temp;}}}}/*求背包的最大价值*/void bag (float w[], float p[], int s[], float volume, int n){int i;float totalV = 0; //总价值for (i = 0; i < n; i++){/*如果当前的容量能装下i物品，则全部装入*/if (volume >= w[s[i]]){volume -= w[s[i]]; //背包的容量减去装入的重量totalV += p[s[i]]; //将当前背包的价值加上装入的物品的价值cout << "重量为" << w[s[i]] << ",价值为" << p[s[i]] << "的物品被全部拿走" << endl;}else{/*如果不能全部装入则装入部分直至全部装满*/totalV += volume/ w[s[i]] * p[s[i]]; //相应的价值按照相应的比例乘以重量cout << "重量为" << w[s[i]] << ",价值为" << p[s[i]] << "的物品拿走" << volume / w[s[i]] << endl;volume = 0;break;}}cout << "能装满的最大价值为：" << totalV << endl;}int main(){int s[20], i;float w[20], p[20]; //w为重量，p为价值cout << "请输入最大重量：" << endl;float volume; //最大重量cin >> volume;cout << "请输入商品的种类数量：" << endl;int n; //商品种类数量cin >> n;cout << "请输入各个商品的重量和价值：" << endl;for (i = 0; i < n; i++){cin >> w[i] >> p[i];}float ave[20]; //ave为单位重量上的价值for (i = 0; i < n; i++){ave[i] = p[i] / w[i]; //重量除以价值}for (i = 0; i < n; i++){/*下标函数*/s[i] = i;}swap(ave, s, n);bag(w, p, s, volume, n);return 0;}
3、贪心算法与动态规划的区别
共同点：两者都具有最优子结构性质
不同点：
1) 动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题时才能做出选择。而贪心算法，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。
2) 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。
总结：
动态规划和贪心算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每用一次贪心准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。当一个问题具有最优子结构时，我们会想到用动态规划法去解它，但是有些问题存在着更简单有效的方法，只要我们总是做出当前看来最好的选择就可以了。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，这使得算法在编码和执行的过程中都有着一定的速度优势。
如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一；但是贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解，与动态规划相比较，它的适用区域相对狭窄许多，因此正确地判断它们的应用时机十分重要。
四、最长公共子串和最长公共子序列
子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串
比如序列bo, bg, lg在母串与中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（,LCS），顾名思义，是指在所有的子序列中最长的那一个。子串是要求更严格的一种子序列，要求在母串中连续地出现。在上述例子的中，最长公共子序列为blog（,），最长公共子串为lo（, ）。
问题描述：求2个字符串的最长公共子串和最长公共子序列。
两道题都可以用动态规划的方法做，只是状态转移方程不同。
五、最长回文子串
回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。回文子串，顾名思义，即字符串中满足回文性质的子串。比如输入字符串 "”，由于该字符串里最长的对称子字符串是 "goog”，因此输出4 。