不知道搜索哪里写的有问题,似乎会死循环qwq,求助大佬!
#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; int a[20],n,W,ans=0x7fffffff; bool b[20],dep; void dfs(int now,int rest,int cnt) {//当前要安排第now只小猫,剩余rest,需用缆车cnt个 if (cnt>=ans) { return; } if (now>n) { ans=cnt; return; } bool flag=0; for(int i=n,last=-1; i; i--) if (!b[i] && rest>=a[i] && a[i]^last) { //a[i]^last是与上一次选的重量不同 flag=1,b[i]=1,last=a[i]; if (a[i]==rest) dfs(now+1,W,cnt+(now<n)); else dfs(now+1,rest-a[i],cnt); b[i]=0; } if (!flag && now<=n) dfs(now,W,cnt+1);//如果没有可选的重量则重新换辆缆车 } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d%d",&n,&W); for (int i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+n+1); dfs(1,W,1); printf("%d",ans); }
全部评论
(0) 回帖