A6192. Cows in a Skyscraper G
编程题
普及+/提高
知识点
题目描述
一个鲜为人知的事实是，Bessie 和她的朋友们喜欢爬楼梯比赛。一个更为人知的事实是，奶牛们真的不喜欢下楼梯。因此，当奶牛们比赛到达她们最喜欢的摩天大楼的顶层后，她们遇到了一个问题。拒绝使用楼梯下楼，奶牛们被迫使用电梯返回地面层。
电梯的最大载重量为 $W$ 磅 $(1 \leq W \leq 100,000,000)$，奶牛 $i$ 的体重为 $C_i$ 磅 $(1 \leq C_i \leq W)$。请帮助 Bessie 找出如何用最少的电梯次数将所有 $N$ 头奶牛 $(1 \leq N \leq 18)$ 送到地面层。每次电梯的总重量不能超过 $W$。
电梯的最大载重量为 $W$ 磅 $(1 \leq W \leq 100,000,000)$，奶牛 $i$ 的体重为 $C_i$ 磅 $(1 \leq C_i \leq W)$。请帮助 Bessie 找出如何用最少的电梯次数将所有 $N$ 头奶牛 $(1 \leq N \leq 18)$ 送到地面层。每次电梯的总重量不能超过 $W$。
输入格式
\* 第 1 行：用空格分隔的 $N$ 和 $W$。
\* 第 2 行到第 $1+N$ 行：第 $i+1$ 行包含一个整数 $C_i$，表示一头奶牛的体重。
\* 第 2 行到第 $1+N$ 行：第 $i+1$ 行包含一个整数 $C_i$，表示一头奶牛的体重。
输出格式
\* 一个整数 $R$，表示所需的最少电梯次数。
输入输出样例
输入 #1
4 10 5 6 3 7
输出 #1
3
说明/提示
有四头奶牛，体重分别为 5、6、3 和 7 磅。电梯的最大载重量为 10 磅。
我们可以将体重为 3 的奶牛与其他任何一头奶牛放在同一个电梯上，但其他三头奶牛太重，无法组合在一起。对于上述解决方案，电梯行程 1 包括奶牛 #1 和 #3，电梯行程 2 包括奶牛 #2，电梯行程 3 包括奶牛 #4。对于此输入，还有其他几种可能的解决方案。
我们可以将体重为 3 的奶牛与其他任何一头奶牛放在同一个电梯上，但其他三头奶牛太重，无法组合在一起。对于上述解决方案，电梯行程 1 包括奶牛 #1 和 #3，电梯行程 2 包括奶牛 #2，电梯行程 3 包括奶牛 #4。对于此输入，还有其他几种可能的解决方案。