0-1背包问题动态规划算法python,动态规划算法经典例题python

　　目录1。导言2。背包问题3。最长非下降子序列

　　1 .简介

　　什么是动态规划

　　动态规划算法通常基于递归公式和一个或多个初始状态。当前子问题的解将从前一个子问题的解中推导出来。用动态规划求解问题只需要多项式时间复杂度，所以比回溯法和暴力法快很多。

　　2.背包问题描述

　　假设我们有n件物品，分别编号为1，2…n。编号为I的物品价值为vi，重量为wi。为了简化问题，假设value和weight都是整数值。

　　现在，假设我们有一个背包，它能承载的重量是w，现在，我们想把这些物品放进包里，让包里的物品价值最大化。

　　那么我们该如何选择包装什么呢？

　　解决方案思维

　　首先，构造状态转移方程。

　　1.我们先创建一个二维数组dp[][]，行：物品类型，列：重量。

　　2.dp[i][j]表示物品类别为I，最大重量为j。

　　可用等式

　　3.当重量足以装下这个物品时，即当j=w[i]，DP [I] [J-W [I]] V [I]，DP [I-1] [J])

　　4.不足时，dp[i][j]=dp[i-1][j]

　　Python代码

　　W=[1，4，3，1] # weight v=[1500，3000，3000，3000]# value N=4 # total weight RES=[[0 for col in range(N-1)]for raw in range(len(V))]def pack(V，W，N):for I in range(len(V)):# weight for J in range(N-1):# weight if J=W[I]:RES[I][J]=max(RES[I-1][J]，RES[J

　　一个序列有N个数字：A[1]，A[2]，…，A[N]。求最长非递减子序列的长度。

　　解决方案思维

　　构建状态转移方程

　　1.创建一个一维数组dp，dp[i]用于存储当前第I个数据的非降序子序列的长度。

　　2.定义一个curlen来表示最长的非降序子序列长度。

　　可获得的方程

　　3.如果args[i]=args[j]然后比较dp[i]=dp[j]，那么dp[i]=dp[j] 1

　　4.这样比较j=range(0，I)后，可以得到dp[i]

　　5.curlen用于存储非降序子序列的最大长度。

　　Python代码：

　　def lis(* args):curnum=1 RES=[0]* len(args)print(len(args))for I in range(len(args)):RES[I]=1 for j in range(I):if args[j]=args[I]and RES[I]RES[j]1:RES[I]=RES[j]1 if RES[I]curnum:curnum=RES[I]print(RES)return curnumprint(lis(5，7，3，4，6，8))

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。