网站建设字体变色代码,进贤网站建设,在线制作图片模板,山西省住房城乡建设厅门户网站一、小明的背包1
试题链接#xff1a;https://www.lanqiao.cn/problems/1174/learning/
问题描述 输入实例
5 20
1 6
2 5
3 8
5 15
3 3
输出示例
37 问题分析
这里我们要创建一个DP表#xff0c;DP#xff08;i#xff0c;j#xff09;表示处理到第i个物品时消耗j体…一、小明的背包1
试题链接https://www.lanqiao.cn/problems/1174/learning/
问题描述 输入实例
5 20
1 6
2 5
3 8
5 15
3 3
输出示例
37 问题分析
这里我们要创建一个DP表DPij表示处理到第i个物品时消耗j体积。这样我们在输入数据时可以直接进行操作。对于每一个dp[i][j]我们都可以转化为求其子问题的最优解即返回到上一次dp[i-1]我们需要注意一个特殊的值dp[i-1][j-w]w为第i个数的体积),我们可以由dp[i-1][j-w]v v为第i个物品的价值)到达dp[i][j]也可以由dp[i-1][j]直接到dp[i][j]这里就分成了两种情况即要么选第i个物品要么不选第i个物品。这样就形成一个dp表我们只需要求出其中的最大值即可。
PS对dp表还可以进行一个空间优化每一个dp[i][j]只和dp[i-1]有关所以我们只需要两个一维列表即可每操作完一个物品就将dp0替换成dp1 代码示例
N,Vmap(int,input().split())
dp[[0]*(V1) for _ in range(N1)]
ans0
for i in range(1,N1):w,vmap(int,input().split())for j in range(V1):if j-w0:dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v)else:dp[i][j]dp[i-1][j]ansmax(ans,dp[i][j])
print(ans)空间优化后的代码
N,Vmap(int,input().split())
dp0[0]*(V1)
dp1[0]*(V1)
ans0
for i in range(1,N1):w,vmap(int,input().split())for j in range(V1):if j-w0:dp1[j]max(dp0[j],dp0[j-w]v)else:dp1[j]dp0[j]ansmax(ans,dp1[j])dp0dp1.copy()
print(ans)二、2022
试题链接https://www.lanqiao.cn/problems/2186/learning/
问题描述 问题分析
这是一道DP问题要三个参数dp[i][j][k]代表判断到第i个数选择了其中j个数和为k共有多少种情况。
对于dp[i][j][k]可以分两种情况①ki这时dp[i][j][k]dp[i-1][j-1][k-i]dp[i-1][j][k]即选择i或不选) ②ki这时dp[i][j][k]dp[i-1][j][k]想加也加不进去
初始条件为dp[i][0][0]1注意dp[0][0][0]也为1否则dp[1][1][1]0 代码示例
V2022
n2022
dp[[[0]*2023 for _ in range(11)] for _ in range(n1)]
dp[0][0][0]1
for i in range(1,n1):dp[i][0][0]1for j in range(1,11):for k in range(1,2023):if ki:dp[i][j][k]dp[i-1][j-1][k-i]dp[i-1][j][k]else:dp[i][j][k]dp[i-1][j][k]
print(dp[2022][10][2022])
#379187662194355221 三、过河卒
试题链接https://www.lanqiao.cn/problems/755/learning/ 输入示例
6 6 3 3
输出示例
6问题分析
对于每一个点ij从起点开始到该点的不同路径为dp[i][j]由题意可得只能从该点左边或上面到达该点所以dp[i][j]dp[i-1][j]dp[i][j-1]。注意不要出界且部分点不能走即可。 代码示例
a,b,c,dmap(int,input().split())
dp[[0]*(b1) for _ in range(a1)]
dp[0][0]1
dp[c][d]-1
he[-2,-2,-1,-1,1,1,2,2]
sh[-1,1,-2,2,-2,2,-1,1]
for _ in range(8):iche[_]jdsh[_]if i0 and j0:dp[i][j]-1
for i in range(a1):for j in range(b1):if dp[i][j]-1:dp[i][j]0else:if i0:dp[i][j]dp[i-1][j]if j0:dp[i][j]dp[i][j-1]
print(dp[a][b])
