做网站属于什么行业,网站制作公司价格,徐州网站开发市场,沈阳看男科的权威医院动态规划
动态规划#xff08;Dynamic Programming#xff0c;简称 DP#xff09;是一种常用于优化问题的算法。它解决的问题通常具有重叠子问题和最优子结构性质#xff0c;可以通过将问题分解成相互依赖的子问题来求解整个问题的最优解。 动态规划算法主要分为以下几个步…动态规划
动态规划Dynamic Programming简称 DP是一种常用于优化问题的算法。它解决的问题通常具有重叠子问题和最优子结构性质可以通过将问题分解成相互依赖的子问题来求解整个问题的最优解。 动态规划算法主要分为以下几个步骤
定义状态将问题描述成一个状态模型包括状态变量和状态转移方程。初始化将状态模型中的变量初始化为特定的值。状态转移根据状态转移方程通过之前的状态计算当前状态的值。计算最优解通过计算得到最终的最优解。
动态规划算法的优点在于它可以避免重复计算因此在处理复杂的问题时特别有用。然而它的缺点在于由于需要存储中间结果它可能需要更多的空间来存储数据。
动态规划经典问题
以下是一些经典的动态规划问题
最长公共子序列LCS给定两个字符串求它们的最长公共子序列。最长递增子序列LIS给定一个序列求它的最长递增子序列。背包问题给定一个背包和一组物品每个物品有重量和价值求在不超过背包容量的情况下能够获得的最大价值。
最长公共子序列LCS
最长公共子序列LCS问题是求解两个序列的最长公共子序列即两个序列中都出现的最长的子序列。下面介绍一种常见的基于动态规划算法的求解方法
令 m 和 n 分别为两个序列的长度令 c[i][j] 表示第一个序列前 i 个元素和第二个序列前 j 个元素的 LCS 的长度则有以下状态转移方程
c[i][j] c[i-1][j-1] 1 (当第一个序列的第 i 个元素等于第二个序列的第 j 个元素时) c[i][j] max(c[i-1][j], c[i][j-1]) (当第一个序列的第 i 个元素不等于第二个序列的第 j 个元素时)
可以看出当两个序列的当前元素相同时LCS 长度加 1否则 LCS 长度不变。因此可以根据这个状态转移方程填充整个 c 数组。
最终LCS 的长度即为 c[m][n]而具体的 LCS 可以通过反向追溯 c 数组得到。具体地从 c[m][n] 开始如果 c[i][j] 等于 c[i-1][j-1] 1则说明第一个序列中第 i 个元素和第二个序列中第 j 个元素都是 LCS 的元素之一将它们加入 LCS 中否则根据 c[i][j] 是否等于 c[i-1][j] 或 c[i][j-1] 确定向左或向上移动。
这个算法的时间和空间复杂度均为 O(mn)。
以下是基于动态规划算法的最长公共子序列LCS问题的 C 代码实现
#include iostream
#include string
#include algorithm
using namespace std;int lcs(string s1, string s2) {int m s1.length(), n s2.length();int c[m1][n1];for (int i 0; i m; i)c[i][0] 0;for (int i 0; i n; i)c[0][i] 0;for (int i 1; i m; i) {for (int j 1; j n; j) {if (s1[i-1] s2[j-1])c[i][j] c[i-1][j-1] 1;elsec[i][j] max(c[i-1][j], c[i][j-1]);}}return c[m][n];
}int main() {string s1 AGGTAB;string s2 GXTXAYB;cout LCS length: lcs(s1, s2) endl;return 0;
}运行结果为
LCS length: 4说明 “GTAB” 是两个序列的最长公共子序列。
最长递增子序列LIS
最长递增子序列Longest Increasing SubsequenceLIS问题是一个经典的动态规划问题。下面是具体的解法及C代码实现。
一、解法
设dp[i]为以第i个元素为结尾的最长递增子序列的长度。dp[i]的值为前i-1个数中所有比第i个数小的数的dp值加1的最大值。
以一个序列 { 534867 }为例
dp[1] 1序列5dp[2] 1序列3dp[3] 2序列34dp[4] 3序列348dp[5] 3序列346dp[6] 4序列3467
二、C代码
#include iostream
#include vector
using namespace std;int lengthOfLIS(vectorint nums) {if (nums.empty()) return 0;int n nums.size();vectorint dp(n, 1); // 其中dp[i]表示以i结尾的最长递增子序列的长度初始值都为1int res 1;for (int i 1; i n; i) { // 遍历到ifor (int j 0; j i; j) { // 遍历到i之前的每个数if (nums[j] nums[i]) {dp[i] max(dp[i], dp[j]1); // 更新最长递增子序列的长度}}res max(res, dp[i]); // 更新最长递增子序列的长度的最大值}return res;
}int main() {vectorint nums {5, 3, 4, 8, 6, 7};cout lengthOfLIS(nums) endl; // 输出4return 0;
}上述代码中使用了vector容器可以方便的实现动态数组。
背包问题
一、01背包问题
给定n个物品和一个容量为W的背包物品i的重量为wt[i]价值为val[i]。现在要求选若干件物品放入背包使得放入的物品总重量不超过W且价值最大。
01背包问题需要使用动态规划求解。设dp[i][j]表示前i个物品中在总重量不超过j的情况下的最大价值。则有以下状态转移方程 如果当前选的物品重量大于当前背包总重量则不能选这个物品dp[i][j] dp[i-1][j] 否则可以选或不选这个物品取决于是否可以使总价值更大 a. 选这个物品总重量为j则总价值为dp[i-1][j-wt[i]]val[i] b. 不选这个物品则总价值为dp[i-1][j] 最终取dp[n][W]即为所求答案。
二、完全背包问题
完全背包问题和01背包问题的区别在于每个物品可以选择无限次。设dp[i][j]表示前i个物品中在总重量不超过j的情况下的最大价值。则有以下状态转移方程 如果当前选的物品重量大于当前背包总重量则不能选这个物品dp[i][j] dp[i-1][j] 否则可以选或不选这个物品取决于是否可以使总价值更大 a. 选这个物品总重量为j则总价值为dp[i][j-wt[i]]val[i] b. 不选这个物品则总价值为dp[i-1][j] 最终取dp[n][W]即为所求答案。
三、多重背包问题
多重背包问题和01背包问题的区别在于每个物品的数量有限制。设dp[i][j]表示前i个物品中在总重量不超过j的情况下的最大价值。则有以下状态转移方程 如果当前选的物品重量大于当前背包总重量则不能选这个物品dp[i][j] dp[i-1][j] 否则可以选或不选这个物品取决于是否可以使总价值更大 a. 选这个物品总重量为j则总价值为dp[i][j-wt[i]]val[i] b. 不选这个物品则总价值为dp[i-1][j] 需要注意的是在更新dp[i][j]的时候需要使用max函数比较选或不选这个物品的价值。同时如果每个物品的数量有限制还需要对物品数量进行处理。最终取dp[n][W]即为所求答案。
四、C代码
01背包问题
#include iostream
#include vector
using namespace std;int knapsack01(int W, vectorint wt, vectorint val) {int n wt.size();vectorvectorint dp(n1, vectorint(W1, 0)); // 初始化为0for (int i 1; i n; i) {for (int j 1; j W; j) {if (wt[i-1] j) { // 当前选的物品重量大于当前背包总重量不能选这个物品dp[i][j] dp[i-1][j];} else {dp[i][j] max(dp[i-1][j], dp[i-1][j-wt[i-1]]val[i-1]); // 取选或不选这个物品的最大价值}}}return dp[n][W];
}int main() {int W 10;vectorint wt {2, 2, 6, 5, 4};vectorint val {6, 3, 5, 4, 6};cout knapsack01(W, wt, val) endl; // 输出15return 0;
}完全背包问题
#include iostream
#include vector
using namespace std;int knapsackCom(int W, vectorint wt, vectorint val) {int n wt.size();vectorvectorint dp(n1, vectorint(W1, 0)); // 初始化为0for (int i 1; i n; i) {for (int j 1; j W; j) {if (wt[i-1] j) { // 当前选的物品重量大于当前背包总重量不能选这个物品dp[i][j] dp[i-1][j];} else {dp[i][j] max(dp[i-1][j], dp[i][j-wt[i-1]]val[i-1]); // 取选或不选这个物品的最大价值}}}return dp[n][W];
}int main() {int W 10;vectorint wt {2, 2, 6, 5, 4};vectorint val {6, 3, 5, 4, 6};cout knapsackCom(W, wt, val) endl; // 输出24return 0;
}多重背包问题
#include iostream
#include vector
using namespace std;int knapsackMul(int W, vectorint wt, vectorint val, vectorint cnt) {int n wt.size();vectorvectorint dp(n1, vectorint(W1, 0)); // 初始化为0for (int i 1; i n; i) {for (int j 1; j W; j) {if (wt[i-1] j) { // 当前选的物品重量大于当前背包总重量不能选这个物品dp[i][j] dp[i-1][j];} else {for (int k 0; k cnt[i-1]; k) { // 对物品数量进行处理if (k*wt[i-1] j) break; // 超过容量退出循环dp[i][j] max(dp[i-1][j], dp[i-1][j-k*wt[i-1]]k*val[i-1]); // 取选或不选这个物品的最大价值}}}}return dp[n][W];
}int main() {int W 10;vectorint wt {2, 2, 6, 5, 4};vectorint val {6, 3, 5, 4, 6};vectorint cnt {2, 3, 1, 4, 3};cout knapsackMul(W, wt, val, cnt) endl; // 输出54return 0;
}
