AcWing 165. 小猫爬山
原题链接
简单
作者:
CqAq
,
2024-04-12 21:55:35
,
所有人可见
,
阅读 11
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 25;
ll n, w;
ll c[N], tmp[N];
int ans = 0x3fffffff;
void dfs(int x, int p){//第i个小猫,第j'个笼子
if(p > ans) return ;//大于之前的答案不合法,直接return
if(x == n + 1){
ans = min(ans, p);
return ;
}
//这里我们枚举每一个笼子,因为例如当我们选取了一组放在一个笼子之后
//可能还剩下一部分空间剩余,所以我们在后面越来越小的体积下,来依次
//补充那些空缺,这样就会最大利用体积,笼子数最少!!!!!
for(int i = 1; i <= p; ++ i){
if(tmp[i] + c[x] <= w){
tmp[i] += c[x];
dfs(x + 1, p);
//if(pta) return ;
tmp[i] -= c[x];//回溯
}
}
//空间初始化
tmp[p + 1] = c[x];
dfs(x + 1, p + 1);
tmp[p + 1] = 0;
//回溯
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> w;
for(int i = 1; i <= n; ++ i) cin >> c[i];
sort(c + 1, c + 1 + n, greater<int>());
dfs(1, 1);//dfs(0,0)也可以,就是c数组从下标0开始
cout << ans;
return 0;
}