设计网站推荐 zoo,网页qq音乐在线听,东莞樟木头网站建设公司,免费空间做自己的网站动态规划#xff08;Dynamic Programming, DP#xff09;是一种算法设计技巧#xff0c;用于解决具有重叠子问题和最优子结构性质的问题。通过将原问题分解为相对简单的子问题的方式来求解复杂问题#xff0c;动态规划避免了计算重复子问题#xff0c;从而提高了算法的效率…动态规划Dynamic Programming, DP是一种算法设计技巧用于解决具有重叠子问题和最优子结构性质的问题。通过将原问题分解为相对简单的子问题的方式来求解复杂问题动态规划避免了计算重复子问题从而提高了算法的效率。
动态规划的关键特点包括
重叠子问题在求解过程中相同的子问题会被多次计算。动态规划通过存储这些子问题的解通常是在一个表格中每个子问题只解决一次以避免不必要的计算。最优子结构一个问题的最优解包含其子问题的最优解。这意味着可以通过组合子问题的最优解来构造原问题的最优解。状态转移方程动态规划算法的核心它描述了问题的状态如何从一个状态转移到另一个状态。状态转移方程通常取决于当前决策和相应的子问题解。
动态规划的步骤通常包括
定义状态确定问题的状态以及状态之间的关系。确定状态转移方程找出状态之间如何转移的规则。初始化条件确定初始状态的值。计算顺序确定计算状态的顺序确保在计算当前状态时所需的子状态已经计算过。构造最优解根据计算出的状态值构造问题的最优解。 动态规划广泛应用于各种领域包括但不限于
最短路径问题如Dijkstra算法和Floyd-Warshall算法。序列对齐问题如生物信息学中的序列对齐。资源分配问题如背包问题。字符串编辑距离如计算两个字符串之间的最小编辑距离。最长公共子序列找出两个序列共有的最长子序列。
动态规划是解决优化问题的强大工具但它要求问题具有重叠子问题和最优子结构的特性。正确识别和定义这些特性是应用动态规划成功的关键。
0-1背包问题 0-1背包问题是动态规划中的经典问题。给定一组物品每种物品都有自己的重量和价值在限定的总重量内选择其中若干个也即每种物品可以选择0个或1个设计选择方案使得物品的总价值最高。 以下是使用动态规划解决0-1背包问题的C语言实现
#include stdio.h
#include stdlib.h// 返回两个整数中的最大值
int max(int a, int b) {return (a b) ? a : b;
}// 动态规划解决0-1背包问题
// 参数W为背包最大容量wt为物品重量数组val为物品价值数组n为物品数量
int knapSack(int W, int wt[], int val[], int n) {int i, w;// 创建一个二维数组dp其中dp[i][w]表示在前i个物品中能够装入容量为w的背包中的最大价值int **dp (int **)malloc((n 1) * sizeof(int *));for (i 0; i n; i) {dp[i] (int *)malloc((W 1) * sizeof(int));}// 填充表格for (i 0; i n; i) {for (w 0; w W; w) {if (i 0 || w 0)dp[i][w] 0;else if (wt[i - 1] w)dp[i][w] max(val[i - 1] dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);elsedp[i][w] dp[i - 1][w];}}// 存储结果int result dp[n][W];// 释放dp数组for (i 0; i n; i) {free(dp[i]);}free(dp);return result;
}// 测试代码
int main() {int val[] {60, 100, 120};int wt[] {10, 20, 30};int W 50;int n sizeof(val) / sizeof(val[0]);printf(背包中物品的最大价值为%d, knapSack(W, wt, val, n));return 0;
}这段代码首先定义了一个max函数用于返回两个整数中的最大值。knapSack函数是动态规划解决0-1背包问题的核心它创建了一个二维数组dp其中dp[i][w]表示在前i个物品中能够装入容量为w的背包中的最大价值。通过填充这个表格最终在dp[n][W]中得到了在给定物品和背包容量限制下的最大价值。最后函数释放了dp数组所占用的内存并返回了最大价值结果。
最长公共子序列问题 最长公共子序列Longest Common Subsequence, LCS问题是寻找两个序列共有的最长子序列的长度这个子序列不需要在原序列中是连续的。以下是使用动态规划解决最长公共子序列问题的C语言实现
#include stdio.h
#include stdlib.h
#include string.h// 返回两个整数中的最大值
int max(int a, int b) {return (a b) ? a : b;
}// 动态规划解决LCS问题
int lcs(char *X, char *Y, int m, int n) {int L[m1][n1];int i, j;// 构建L[m1][n1]以便保存LCS的长度for (i 0; i m; i) {for (j 0; j n; j) {if (i 0 || j 0)L[i][j] 0;else if (X[i-1] Y[j-1])L[i][j] L[i-1][j-1] 1;elseL[i][j] max(L[i-1][j], L[i][j-1]);}}// L[m][n]包含了X[0..m-1]和Y[0..n-1]的LCS的长度return L[m][n];
}// 打印LCS这是一个辅助函数
void printLCS(char *X, char *Y, int m, int n) {int index lcs(X, Y, m, n);char lcs[index1];lcs[index] \0; // 设置字符串的终止符int i m, j n;while (i 0 j 0) {if (X[i-1] Y[j-1]) {lcs[index-1] X[i-1]; // 如果当前字符在LCS中i--; j--; index--; // 减少值}else if (L[i-1][j] L[i][j-1])i--;elsej--;}// 打印LCSprintf(LCS of %s and %s is %s\n, X, Y, lcs);
}// 测试代码
int main() {char X[] AGGTAB;char Y[] GXTXAYB;int m strlen(X);int n strlen(Y);printf(Length of LCS is %d\n, lcs(X, Y, m, n));// 如果需要打印LCS取消注释下面的行// printLCS(X, Y, m, n);return 0;
}这段代码首先定义了一个max函数用于返回两个整数中的最大值。lcs函数是动态规划解决LCS问题的核心它创建了一个二维数组L其中L[i][j]表示字符串X[0…i-1]和Y[0…j-1]的LCS的长度。通过填充这个表格最终在L[m][n]中得到了两个字符串的LCS的长度。
请注意上述代码中的printLCS函数用于打印LCS但由于它依赖于L数组而L数组在lcs函数中是局部变量直接使用printLCS函数可能会导致编译错误。为了使printLCS函数正常工作需要对代码进行适当的修改以便能够访问或重新计算L数组的值。这里提供的printLCS函数主要是为了展示如何根据L数组回溯找到LCS实际使用时需要注意这一点。
