动态规划求解最长公共子序列与0-1背包问题

本次实验是关于使用动态规划方法解决最长公共子序列问题和0-1背包问题。实验目的是深入理解动态规划的核心思想、求解策略和步骤，并通过算法设计、描述、正确性证明、复杂性分析及实现进行实践。 动态规划法求解最长公共子序列问题: 1. 问题描述: 输入是两个字符串X和Y，输出是它们的最长公共子序列Z。例如，X={A,B,C}，Y={A,C,D}，Z={A,C}。 2. 算法设计: - 数据结构: 使用二维数组c存储子问题的最优解，b数组记录最优解来源。 - 初始化: c[i][0] = 0, c[0][j] = 0，其中0 ≤ i ≤ m, 0 ≤ j ≤ n，m和n分别是X和Y的长度。 - 循环阶段: 依据递归关系计算Xi和Yj的LCS长度，遍历所有i和j。 - 构造最优解: 通过b数组信息自底向上回溯构建LCS。 伪代码: ``` LCS(X, Y): m = length(X) n = length(Y) c = [m+1][n+1] // 初始化为0 b = [m+1][n+1] // 初始化为0 FOR i = 1 TO m FOR j = 1 TO n IF X[i-1] == Y[j-1] c[i][j] = c[i-1][j-1] + 1 b[i][j] = 'match' ELSE c[i][j] = max(c[i-1][j], c[i][j-1]) IF c[i-1][j] > c[i][j-1] b[i][j] = 'drop X' ELSE b[i][j] = 'drop Y' // 回溯构造LCS result = "" i = m j = n WHILE i > 0 AND j > 0 IF b[i][j] == 'match' result = X[i-1] + result i -= 1 j -= 1 ELSE IF b[i][j] == 'drop X' i -= 1 ELSE j -= 1 RETURN result ``` 0-1背包问题: 1. 问题描述: 给定一组物品，每种物品都有重量和价值，背包有固定容量，目标是选择物品以最大化总价值，但每个物品只能放0个或1个。 2. 算法设计: - 数据结构: 用二维数组dp表示状态，dp[i][w]表示前i个物品放入容量为w的背包能获得的最大价值。 - 初始化: dp[0][w] = 0，表示没有物品时背包价值为0。 - 循环阶段: 对每个物品i和每个容量w，决定是否将物品i放入背包，更新dp[i][w]。 伪代码: ``` 01_Knapsack(W, items): n = length(items) dp = [n+1][W+1] // 初始化为0 FOR i = 1 TO n FOR w = 1 TO W IF items[i-1].weight <= w dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i-1].weight] + items[i-1].value) ELSE dp[i][w] = dp[i-1][w] RETURN dp[n][W] ``` 实验步骤涵盖从问题理解到算法实现的全过程，包括问题描述、算法设计、正确性证明、复杂性分析、代码实现和测试，以及个人心得。通过这个实验，学生能够深入理解动态规划在解决这类问题中的应用，并提高分析和解决问题的能力。