主题网站的设计方案,网页设计模板及代码,建设公司网站需要准备哪些材料,c网站开发案例详解 pdf文章目录 前言一、动态规划动态规划的基本步骤示例1示例2 三、代码实现----Matlab1.示例12.示例2 四、代码实现----python1.示例12.示例2 总结 前言
通过模型算法#xff0c;熟练对Matlab和python的应用。 学习视频链接#xff1a; https://www.bilibili.com/video/BV1EK411… 文章目录 前言一、动态规划动态规划的基本步骤示例1示例2 三、代码实现----Matlab1.示例12.示例2 四、代码实现----python1.示例12.示例2 总结 前言
通过模型算法熟练对Matlab和python的应用。 学习视频链接 https://www.bilibili.com/video/BV1EK41187QF/?p32vd_source67471d3a1b4f517b7a7964093e62f7e6
一、动态规划
动态规划Dynamic Programming简称 DP是一种在计算机科学和数学中用于解决复杂问题的优化技术。它通过将问题分解为更小的子问题存储这些子问题的解以避免重复计算从而提高算法的效率。动态规划通常用于具有重叠子问题和最优子结构性质的问题。
动态规划的基本步骤
定义状态: 确定一个数组或其他数据结构来存储子问题的解。这个数组的每个元素代表一个子问题的解。状态转移方程: 找到子问题之间的关系定义一个递归关系状态转移方程来表示大问题和小问题之间的关系。初始化: 确定初始条件即基础子问题的解。计算顺序: 通常是自底向上从子问题到原问题计算所有子问题的解。
示例1
硬币问题
你有三种硬币分别面值2元、5元和7元的硬币组合起来正好付清不需要对方找钱每种硬币都有足够多买一本书需要27元如何用最少 定义状态: 虽然不知道最优策略是什么但是最优策略肯定是有 k k k 枚硬币 a 1 , a 2 , … a n a_1,a_2,… a_n a1,a2,…an 加起来面值为27所以一定存在有最后一枚硬币 a k a_k ak 。除了这枚硬币前面硬币的面值加起来是 27 − a k 27- a_k 27−ak 子问题 最少用多少枚硬币可以拼出 27 − a k 27- a_k 27−ak原问题是最少用多少枚硬币可以拼出 27我们将原问题可以转化成一个规模更小的子问题 27 − a k 27- a_k 27−ak状态我们可以设状态 f ( x )最少用多少枚硬币拼出 x 状态转移方程: 初始化: 初始条件 f [ 0 ] 0 f[0]0 f[0]0 计算顺序: 计算 f [ 0 ] , f [ 1 ] , f [ 2 ] , . . . f [ x ] f[0],f[1],f[2],...f[x] f[0],f[1],f[2],...f[x] 当计算到 f [ x ] f[x] f[x] 时 f [ x − 2 ] , f [ x − 5 ] , f [ x − 7 ] f[x-2],f[x-5],f[x-7] f[x−2],f[x−5],f[x−7] 都已经算过了。
示例2
背包问题
给定 n n n 个物品每个物品有一个重量 w i w_i wi 和一个价值 v i v_i vi。给定一个背包的最大承重 W W W求解如何选择物品放入背包使得在不超过最大承重的前提下背包中的物品总价值最大。 定义状态: d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i 件物品放入容量为 j j j 的背包中所获得的最大价值 状态转移方程: 对于第 i i i 件物品可以选择放或不放 如果不放那么 d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j]dp[i-1][j] dp[i][j]dp[i−1][j] 如果放那么 d p [ i ] [ j ] d p [ i − 1 ] [ j − w i ] v i dp[i][j]dp[i-1][j-w_i]v_i dp[i][j]dp[i−1][j−wi]vi 选择获得最大价值的情况即 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w i ] v i ) dp[i][j]max(dp[i-1][j],dp[i-1][j-w_i]v_i) dp[i][j]max(dp[i−1][j],dp[i−1][j−wi]vi) 初始化: 初始条件 d p [ 0 ] [ 0 ] 0 dp[0][0]0 dp[0][0]0将前 0 个物品放入容量为 0 的背包中能获得的最大价值为 0 如果容量为 0则无法放入任何物品 d p [ i ] [ 0 ] 0 dp[i][0]0 dp[i][0]0 如果没有物品可选则无法放入任何物品 d p [ 0 ] [ j ] 0 dp[0][j]0 dp[0][j]0。 计算顺序: 从第一个物品开始求解到 n n n 最终 d p [ n ] [ W ] dp[n][W] dp[n][W] 即为问题的解
三、代码实现----Matlab
1.示例1
clear;clc
n input(请输入要拼的金额:) 1;
res coinChange(n);
disp([需要 int2str(res) 枚硬币])function res coinChange(n)dp ones(n,1) * inf;dp(1) 0; % 要拼出0块钱需要0枚硬币for i 2:nif (i 3)dp(i) min(dp(i),dp(i-2) 1); endif (i 6)dp(i) min(dp(i),dp(i-5) 1); endif (i 8)dp(i) min(dp(i),dp(i-7) 1);endendif dp(n) ~ infres dp(n);elseres -1;end
end
运行结果 2.示例2
clear;clc
c input(请输入背包的容量:);
weight input(请输入每件物品的重量:);
value input(请输入每件物品的价值:);
res bag_value(c,weight,value);
disp([最大价值为: int2str(res)])function res bag_value(c,w,v) % c是背包容量,w是每件物品的重量,v是每件物品的价值n length(w); % n代表有多少件物品dp zeros(n1,c1);for i 2:n1 % 第i-1个物品for j 2:c1 % j-1是容量if j-1 w(i-1) % 背包容量小于当前物品重量不能选择当前物品dp(i,j) dp(i-1,j);else % 能选择当前物品要选择价值更大的方案dp(i,j) max(dp(i-1,j),dp(i-1,j-w(i-1))v(i-1));endendendres dp(n1,c1);
end运行结果 四、代码实现----python
1.示例1
# 硬币问题
def coinChange(n):dp [float(inf)] * (n 1)dp[0] 0 # 要拼出0块钱需要0枚硬币for i in range (1,n 1):if (i 2):dp[i] min(dp[i],dp[i-2]1)if (i 5):dp[i] min(dp[i],dp[i-5]1)if (i 7):dp[i] min(dp[i],dp[i-7]1)if dp[n] ! float(inf):return dp[n]else:return -1n int(input(请输入要拼的金额:))
print(要拼的金额, n,元)
print(需要, coinChange(n),枚硬币)运行结果 2.示例2
# 背包问题
def bag_value(c,w,v):n len(w)dp [[0 for j in range(c 1)] for i in range(n1)] # 初始化动态规划数组for i in range(1,n 1):for j in range(1,c1): if j w[i-1]: # 背包容量小于当前物品重量不能选择当前物品dp[i][j] dp[i-1][j]else: # 能选择当前物品要选择价值更大的方案dp[i][j] max(dp[i-1][j],dp[i-1][j-w[i-1]]v[i-1])return dp[n][c]
c int(input(请输入背包的容量:))
weight input(请输入每件物品的重量,用逗号隔开:)
value input(请输入每件物品的价值,用逗号隔开:)
w [int(x) for x in weight.split(,)]
v [int(x) for x in value.split(,)]
print(背包的容量:,c)
print(每件物品的重量:,w)
print(每件物品的价值:,v)
print(最大价值为:,bag_value(c,w,v))运行结果 总结
本文介绍了动态规划并通过典型示例建立模型分别使用Matlab和python进行代码编写。
