小猫爬山（dfs 剪枝

添加链接描述

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;intN,W,ans=0x3f3f3f3f;intweight[20];intcar[20];voiddfs(intnum,intcnt){if(cnt==ans+1){//超过当前最优解return;}if(num==N+1){ans=min(ans,cnt);return;}for(inti=1;i<=cnt;i++){if(car[i]+weight[num]<=W){//要小于等于// cout<<num<<" "<<cnt<<" "<<car[i]<<"\n";car[i]+=weight[num];dfs(num+1,cnt);car[i]-=weight[num];//不选要减少全局变量记录的}}car[cnt+1]+=weight[num];dfs(num+1,cnt+1);car[cnt+1]-=weight[num];}intmain(){cin>>N>>W;for(inti=1;i<=N;i++){cin>>weight[i];}ans=N;//最差情况sort(weight+1,weight+N+1,greater<int>());dfs(1,1);cout<<ans<<"\n";return0;}