济南专业做网站近期新闻事件
一、小明的背包2
试题链接：https://www.lanqiao.cn/problems/1175/learning/
输入示例
5 20
1 6
2 5
3 8
5 15
3 3 输出示例
120问题分析
这题是完全背包，每个物品有无数个，所以对于任意dp[i][j]（其表示的意思为选到第i个物品时所消耗的体积为j），当j>=i的体积时，其可以从三个状态转移过来，①dp[i-1][j]（表示一次也不选i）②dp[i-1][j-w]+v （表示第一次选i）③dp[i][j-w]+v（表示不一定第一次选i），把②去掉答案也是对的；当j<i时，只能从dp[i-1][j]转移来啦。
代码示例
N,V=map(int,input().split())
dp=[[0]*(V+1) for _ in range(N+1)]
for i in range(1,N+1):w,v=map(int,input().split())for j in range(1,V+1):if j-w>=0:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v,dp[i][j-w]+v)else:dp[i][j]=dp[i-1][j]
print(dp[N][V])
二、最长公共子序列
试题链接：https://www.lanqiao.cn/problems/1189/learning/
输入示例
5 6
1 2 3 4 5
2 3 2 1 4 5输出示例
4问题分析
dp[i][j]表示数组A处理到第i个数，数组B处理到第j个数时他们的最大公共子序列的长度。分为两种情况：①a[i]==b[j]，那么dp[i][j]=dp[i-1][j-1]+1；②a[i]!=b[j]，dp[i][j]=max(dp[i-1][j],dp[i][j-1])
代码示例
N,M=map(int,input().split())
a=[0]+input().split()
b=[0]+input().split()
dp=[[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):for j in range(1,M+1):if a[i]==b[j]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[N][M])