公共子序列问题

 ~待补充

最长公共子序列

对于两个字符串A和B，A的前i位和B的前j位的最大公共子序列必然是所求解的一部分，设dp[i][j]为串A前i位和B串前j位的最长公共子序列的长度，则所求答案为dp[n][m]，其中n，m分别为字符串A和B的长度，若A[i]=B[j]，则该元素可以作为之前构造的公共子序列的下一位元素，dp[i][j]=dp[i-1][j-1]+1，同时判断当前记录的最长子串的结果maxlen与dp[i][j]的大小，若是大于当前的最大值maxlen，则更新maxlen的值，同时记录索引位置index。直到所有遍历完毕，得到最长子串的末尾索引和长度，可以求取子串。

代码如下：

class Solution {
public:/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/string LCS(string str1, string str2) {// write code hereint len1=str1.size();int len2=str2.size();vector<vector<int>>dp(len1+1,vector<int>(len2+1));int index=0,maxlen=0;for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(str1[i-1]==str2[j-1]){dp[i][j]=dp[i-1][j-1]+1;if(dp[i][j]>maxlen){maxlen=dp[i][j];index=i-1;}}}}return str1.substr(index-maxlen+1,maxlen);}
};

背包问题

0-1背包问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

注意特点是：每种物品仅有一件，可以选择放或不放。

f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{ f[i-1][v],w[i]+f[i-1][v-c[i]] }

解释：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个放前i-1件物品的问题。

• 如果不放第 i 件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；
• 如果放第 i 件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

【因为决定放第 i 件物品意味着背包要被占用 c[i] 容量并获得w[i]得价值，因此问题变为将前i-1件物品放入剩下的容量为v-c[i]的背包中获得的最大价值f[i-1][v-c[i]] 】

代码如下：

class Solution {
public:/*** 计算01背包问题的结果* @param V int整型 背包的体积* @param n int整型 物品的个数* @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi* @return int整型*/int knapsack(int V, int n, vector<vector<int> >& vw) {// write code hereif(V<=0||n<=0||vw.empty()) return 0;vector<vector<int>>dp(n+1,vector<int>(V+1,0));//dp[i][j]表示前i件物品装入j容量的包里最大价值for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j<vw[i-1][0])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],vw[i-1][1]+dp[i-1][j-vw[i-1][0]]);}}return dp[n][V];}
};