翰翰和达达饲养了 只小猫,这天,小猫们要去爬山。
经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 ,而 只小猫的重量分别是 。
当然,每辆缆车上的小猫的重量之和不能超过 。
每租用一辆缆车,翰翰和达达就要付 美元,所以他们想知道,最少需要付多少美元才能把这 只小猫都运送下山?
输入格式
第 行:包含两个用空格隔开的整数, 和 。
第 行:每行一个整数,其中第 行的整数表示第 只小猫的重量 。
输出格式
输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。
数据范围
输入样例:
5 1996
1
2
1994
12
29
输出样例:
2
思路
搜索顺序类似于分成互质组, 枚举组数。
这里剪枝是终点: 首先看能不能优化搜索顺序, 先放轻的猫还是先放重的猫。显然是重的猫分支少。 故这里把猫排序, 从重的开始枚举。
代码
const int N = 20;
int n, w;
int a[N];
int sum[N];
int ans = 20;
void dfs(int u, int k)
{
if (k >= ans)
return;
if (u == n)
{
ans = k;
return;
}
for (int i = 0; i < k; i++)
{
if (sum[i] + a[u] <= w)
{
sum[i] += a[u];
dfs(u + 1, k);
sum[i] -= a[u];
}
}
sum[k] = a[u];
dfs(u + 1, k + 1);
sum[k] = 0;
}
int main()
{
cin >> n >> w;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n, greater<int>());
dfs(0, 0);
cout << ans << endl;
return 0;
}