题目链接：https://ac.nowcoder.com/acm/contest/1014/A
Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1,C2…CNC_1,C_2\dots C_NC1?,C2?…CN?。
当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i只小猫的重量CiC_iCi?。
5 1996
1
2
1994
12
29
2
素数环相当与一个萝卜一个坑，小猫爬山就是一个坑多个萝卜，求出最少的用的坑数。并且素数环是针对每个坑搜索，看第step个坑放哪个数；
小猫爬山是针对第step个数通过遍历找到适合他的坑，没有适合的就需要重新建立一个坑。
值得一提的是，通过提交测试在减枝时写成if(cnt>res)比写成if(cnt>=res)慢很多，前者时间大概在300ms,后者为4ms;由此可见，剪枝很重要，
正确剪枝更为重要。
AC代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 #define Max 0x3f3f3f3f 4 using namespace std; 5 6 int n, w,res,ans[20],pit[25]; 7 8 bool cmp(int a,int b) { 9 return a > b; 10 } 11 //step当前处理为第几个cat，cnt处理了step-1个猫用的车数 12 void dfs(int step,int cnt) { 13 if (cnt >= res) 14 return; 15 if (step == n + 1) { 16 res = min(res,cnt); 17 return; 18 } 19 20 //在现有的车中找适合第step只猫的车 21 for (int i = 1; i <= cnt; i++) { 22 if (pit[i] + ans[step] <= w) { 23 pit[i] += ans[step]; 24 dfs(step+1,cnt); 25 pit[i] -= ans[step]; 26 } 27 } 28 //在现有的车中找不到合适的车新增一辆，并将猫放入其中 29 pit[cnt + 1] = ans[step]; 30 dfs(step+1,cnt+1); 31 } 32 33 int main(void) 34 { 35 scanf("%d%d",&n,&w); 36 for (int i = 1; i <= n; i++) 37 scanf("%d",&ans[i]); 38 sort(ans+1,ans+1+n,cmp); 39 res = Max; 40 dfs(1,1); 41 printf("%d\n",res); 42 43 return 0; 44 }
原文：https://www.cnblogs.com/gn1314/p/11416238.html