AcWing 165. 小猫爬山
原题链接
简单
作者:
神人
,
2024-04-10 15:56:39
,
所有人可见
,
阅读 5
python 代码
import sys
# n表示小猫的数量 w表示每辆缆车的承重
n, w = map(int, input().split())
a = [0] * (n + 1) # 数组a中从下表1 到 n + 1 依次表示每只小猫的重量
p = [0] * (n + 1) # 数组p的每一个元素表示当前每一辆缆车已承重多少
ans = sys.maxsize # ans表示最后所需要的最少缆车数量 初始化为最大值
# x表示当前是第几只小猫 cnt表示当前已经开辟了多少辆缆车
def dfs(x, cnt):
global ans
if cnt >= ans: # 这一次回溯得到的cnt数量 >= ans 没必要更新 直接返回
return
if x == n + 1: # 此时已经遍历完了所有小猫 更新ans的值 直接返回
ans = min(ans, cnt)
return
for i in range(1, cnt + 1): # 遍历目前所有已经开辟的小车 尝试每次能否将当前小猫放进去 不断更新ans
if p[i] + a[x] <= w:
p[i] += a[x]
dfs(x + 1, cnt) # 可以放进去 最终会得到一个新的ans
p[i] -= a[x] # 尝试放进另一个缆车里 所以需要回溯一下
# 放不进去开辟的小车里 所以需要新开辟一辆
p[cnt + 1] = a[x]
dfs(x + 1, cnt + 1) # 小车数量 + 1
p[cnt + 1] = 0
for i in range(1, n + 1): # 输入每只小猫的重量
a[i] = int(input())
a = [0] + sorted(a[1:n+1], reverse=True) # 对小猫按重量从大到小排序 将大的先放进去 否则大的后放有可能需要多开辟缆车
dfs(1, 0) # 计算ans
print(ans)