DFS

直觉上, 应该优先安排体重大的猫, 因此, 对猫从大到小排序.
将最重的猫放到第一辆车子里面. 然后用dfs安排其他的猫.
对第i个猫, 要么放到已租的其中一个缆车里面(如果放得下), 要么新租一个缆车.
剪枝技巧:
1. 刚刚提到的, 根据猫的体重(从大到小)依次安排缆车, 因为体重小的猫总是可以见缝插针.
2. 如果已有的缆车数量大于等于当前找到的最优答案, 那么可以回溯了.

Python 代码

def dfs(idx):
    global ans
    if len(bus) >= ans:
        return
    if idx >= N:
        ans = len(bus)
        return
    for i in range(len(bus)):
        if bus[i] + C[idx] <= W:
            bus[i] += C[idx]
            dfs(idx + 1)
            bus[i] -= C[idx]
    bus.append(C[idx])
    dfs(idx + 1)
    bus.pop()

N, W = map(int, input().split())
C = []
for _ in range(N):
    C.append(int(input()))
C.sort(reverse=True)
bus = []
bus.append(C[0])
ans = N
dfs(1)
print(ans)