【蓝桥Python每日一练】————砝码称重

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

---

题目

 

题解

难度系数：⭐⭐⭐

考察题型：动态规划

涉及知识点：状压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种情况：b   b+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())#3a=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]=1 dp[2][1]=1 dp[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:0 1 2 3 4 5 6 7 8 9 10 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]+adp=[[0]*(sum(a)+1) for _ in range(n+1)]dp[0][0]=1for 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]]=1print(sum(dp[n])-1)

---

 读码上万行，下键如有神，撸起袖子加油干！