备战蓝桥杯|【蓝桥Python每日一练】————砝码称重（状压DP） python|蓝桥杯|职场和发展|算法

文章图片
大家好，我是爱学习的小蓝，欢迎交流指正~
文章图片

文章图片

题目传送门：蓝桥杯2021年第十二届省赛真题-砝码称重 - C语言网

文章图片

文章图片

文章图片

题解难度系数：???
考察题型：动态规划
涉及知识点：状压DP

第一步：明白dp[i][j]的含义

dp[i]#放置第i个砝码后出现的所有情况 dp[i][j]#代表是否取这个值 0和1表示

第二步：给dp数组初始化赋值

dp=[[0]*(sum(a)+1) for _ in range(n+1)] #(sum(a)+1)列(n+1)行存放砝码1和0的情况 dp[0][0]=1#初始化一个砝码情况时为1

第三步：弄清dp[j]遍历的顺序

for i in range(1,n+1):#n个砝码对应n种情况 for j in range(sum(a)+1): #遍历0~sum(a)的所有可能重量

第四步：搞懂递推公式
假设之前的砝码重量为a[i]，当前砝码重量为b
那么现在的重量有3种情况：bb+a[i]b-a[i]

if dp[i-1][j]==1:#如果前一组砝码已经选择 dp[i][j]=1#选择当前砝码 dp[i][j+a[i]]=1#选择（当前砝码+之前砝码） if j>a[i]:#当前砝码>之前砝码 dp[i][j-a[i]]=1#选择（当前砝码-之前砝码）

第五步：打印数组

print(sum(dp[n])-1)#最后一组中选择的情况求和-特殊情况（给0赋值的1）

代码详细注释版

#砝码称重 n=int(input())#3 a=list(map(int,input().split()))#[1,4,6] a.sort(reverse=True)#[6,4,1] a=[0]+a#[0,6,4,1] dp=[[0]*(sum(a)+1) for _ in range(n+1)] dp[0][0]=1 #[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] for i in range(1,n+1):#1,2,3 for j in range(sum(a)+1): #0~11 if dp[i-1][j]==1:#dp[1-1][0]=1 dp[2-1][0]=1 dp[2-1][6]=1 dp[i][j]=1#dp[1][0]=1dp[2][1]=1dp[2][6]=1 dp[i][j+a[i]]=1#dp[1][0+6]=1 dp[2][1+4]=1 dp[2][6+4]=1 if j>a[i]:#6>4 dp[i][j-a[i]]=1#dp[1][6-4]=1 #index:012345678910 11 #0: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #1: [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], #2: [1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0], #3: [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1] print(sum(dp[n])-1)#10

精简代码版

n=int(input()) a=list(map(int,input().split())) a.sort(reverse=True) a=[0]+a dp=[[0]*(sum(a)+1) for _ in range(n+1)] dp[0][0]=1 for i in range(1,n+1): for j in range(sum(a)+1): if dp[i-1][j]==1: dp[i][j]=1 dp[i][j+a[i]]=1 if j>a[i]: dp[i][j-a[i]]=1 print(sum(dp[n])-1)