题目描述
翰翰和达达饲养了N只小猫,这天,小猫们要去爬山。
经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为W,而N只小猫的重量分别是C1、C2……CN。
当然,每辆缆车上的小猫的重量之和不能超过W。
每租用一辆缆车,翰翰和达达就要付1美元,所以他们想知道,最少需要付多少美元才能把这N只小猫都运送下山?
样例
输入样例:
5 1996
1
2
1994
12
29
输出样例:
2
算法1
(暴搜)
优化方法:
1. 如果当前篮子数比已经求解的篮子数要大,直接return
2. 从重量比较大的猫开始枚举,可以减少搜索次数。(重的小猫和轻的小猫都会枚举到,把重的放前面)
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, m;
int sum[N], cat[N];
int ans = N;
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] + cat[u] <= m){
sum[i] += cat[u];
dfs(u + 1, k);
sum[i] -= cat[u];
}
sum[k] = cat[u];
dfs(u + 1, k + 1);
sum[k] = 0;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; i ++) cin >> cat[i];
sort(cat, cat + n);
reverse(cat, cat + n);
dfs(0, 0);
cout << ans << endl;
return 0;
}