缆车
2025-04-02 20:51:48
发布于：上海
3阅读
0回复
0点赞
食用说明:自食,不建议他人食用
缆车:
题目大意:
有n个同学,体重为C1,C2...Cn.缆车的承重量为w.
问把所有同学都送上缆车最少需要多少量缆车.
解题思路:
深度优先搜索中的01DFS的变种.
一个同学一个同学的往缆车里放.
每放完一个同学就开一辆新缆车.
每次递归枚举的是把一个同学往每一辆缆车里放.
枚举所有情况.
链接
代码:
#include<bits/stdc++.h>
using namespace std;
int n,w;
int a[20];
int q[20];
int answer=20;
void dfs(int x,int sum){
if(sum>=answer)return;
if(x==n+1){
answer=min(answer,sum);
return;
}
for(int i=1;i<=sum;i++){
if(q[i]+a[x]<=w){
q[i]+=a[x];
dfs(x****um);
q[i]-=a[x];
}
}
q[sum+1]=a[x];
dfs(x****um+1);
q[sum+1]=0;
}
int main(){
cin>>n>>w;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(1,0);
cout<<answer;
}
这里空空如也
有帮助，赞一个