【题目来源】
蓝桥云课：1.买瓜 - 蓝桥云课
【题目描述】
小蓝正在一个瓜摊上买瓜。瓜摊上共有 \(n\) 个瓜，每个瓜的重量为 \(A_i\)。
小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 \(m\)。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 \(m\) 的瓜。如果无论怎样小蓝都无法得到总重恰好为 \(m\) 的瓜，请输出\(-1\)。
【输入】
输入的第一行包含两个整数 \(n,m\)，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含 \(n\) 个整数 \(A_i\)，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。
【输出】
输出一行包含一个整数表示答案。
【输入样例】
3 10
1 3 13
【输出样例】
2
【代码详解】
def dfs(depth, weight, cnt):#depth：第depth个瓜#weight：表示当前买到的瓜的重量#cnt：表示当前劈的次数#剪枝，当前已经不合法，没必要继续下去if weight>m:returnif weight == m:global ansans = min(ans, cnt)if depth == n:return#枚举当前瓜的三种情况#不买dfs(depth+1, weight+0, cnt)#买dfs(depth+1, weight+A[depth], cnt)#买一半dfs(depth+1, weight+A[depth]//2, cnt+1)n, m = map(int, input().split())
m *= 2
A = list(map(int, input().split()))
A = [x*2 for x in A]
ans = n + 1
dfs(0, 0, 0)
if ans == n+1:ans = -1
print(ans)
【运行结果】
3 10
1 3 13
2