问题描述:你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1, W2, · · · WN
请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边
输入的第一行包含一个整数 N
第二行包含 N 个整数:W1, W2, W3, · · · WN输出一个整数代表答案
输出一个整数代表答案
样例输入
3
1 4 6
样例输出
10
思路解析:这道题采用两种方法。
第一种是常规的循环遍历,将各种可能的情况写入列表,计算其长度求解。
ans=set() #集合的特点去重
n=int(input())
s=list(map(int,input().split()))
ans.add(s[0]) #集合把第一个砝码加进去方便第一次计算
for i in range(1,n):
a=[] #用来存储每一次加or减的结果
for j in ans:
a.append(j+s[i])
a.append(abs(j-s[i]))
for k in a:
if k!=0: #重量不能为0
ans.add(k)
ans.add(s[i]) #当前砝码加入集合
print(len(ans))
第二种是用动态规划的思想,设置一个状态dp[p][q],来表示取到第p个砝码,q重量能否被测出。用0和1代表False 和True,最后计算出dp表1的数量即可。
难点:dp状态转移方程(需考虑多种情况)
a[p-1]代表新加入这个砝码的重量,如果与这个未知量q相等,则dp值为1
dp[p-1]代表一个集合X(已知或者说已经测出来的数据集合),dp[p-1][a[p-1]+q]就表示,在集合X中是否有一个数等于a[p-1]+q,如果有则dp[p-1][a[p-1]+q]这个式子存在,令dp值为1。
dp[p-1][abs(a[p-1]-q)]表示在集合X中是否有一个数等于a[p-1]-q的绝对值,如果有则dp[p-1][abs(a[p-1]-q)]这个式子存在,令dp值为1
最后就是遍历dp表中为1的数,代表可以表示重量的个数
n=int(input())
a=list(map(int,input().split()))
sum=0
for i in a: #确定q的最大取值范围sum
sum+=i
ans=0
dp=[[0]*2*sum for i in range(n+1)] #前列后行,只要行列满足最大范围即可,可*3或4等等
for p in range(1,n+1):
for q in range(1,sum+1):
dp[p][q]=dp[p-1][q] #假设加到第三个砝码就可以测出来q,就不必再加第四个砝码,令其dp值为1,则后面的if语句不再执行
if dp[p][q]==0:
if a[p-1]==q:
dp[p][q]=1
if dp[p-1][a[p-1]+q]:
dp[p][q]=1
if dp[p-1][abs(a[p-1]-q)]:
dp[p][q]=1
for i in dp[n]:
if i != 0:
ans+=1
print(ans)
感觉还是有很多不足,欢迎大家来指点