C超级书架深度优先搜索Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架尽管它是如此的大但它还是几乎瞬间就被各种各样的书塞满了。现在只有书架的顶上还留有一点空间。 所有 )N(1≤N≤20) 头奶牛都有一个确定的身高 Hi (1≤Hi≤1,000,000)。设所有奶牛身高的和为 S。书架的高度为 B并且保证 1≤B≤S。 为了够到比最高的那头奶牛还要高的书架顶奶牛们不得不象演杂技一般一头站在另一头的背上叠成一座“奶牛塔”。当然这个塔的高度就是塔中所有奶牛的身高之和。为了往书架顶上放东西所有奶牛的身高和必须不小于书架的高度。 塔叠得越高便越不稳定于是奶牛们希望找到一种方案使得叠出的塔在高度不小于书架高度的情况下高度尽可能小。你也可以猜到你的任务了写一个程序计算奶牛们叠成的塔在满足要求的情况下最少要比书架高多少。输入格式第 1 行: 2 个用空格隔开的整数N 和 B。第 2.N1 行: 第 i1 行是 11 个整数H_iHi。输出格式输出 1 个非负整数即奶牛们叠成的塔最少比书架高的高度。输出时每行末尾的多余空格不影响答案正确性要求使用「文件输入输出」的方式解题输入文件为 shelf.in输出文件为 shelf.out样例输入5 1631356样例输出1本题可用01背包来做也可用深度优先搜索这里用深度优先搜索用 DFS 枚举所有的可能求出超过书架的最小距离。#includeiostream#includecstdio#includealgorithmusingnamespacestd;intn,b,h[22],sum[22],ans1e7;voiddfs(intx,intdep,intnum){if(numb)ansmin(ans,num-b);//coutendlans\n;}//coutnumendl;if(x0)return;sum[dep]h[x];//coutsum[dep] ;dfs(x-1,dep1,numsum[dep]);dfs(x-1,dep,num);}intmain(){freopen(shelf.in,r,stdin);freopen(shelf.out,w,stdout);cinnb;for(inti0;in;i)cinh[i];//sort(,xn);dfs(n,0,0);cout/*endl*/ans;return0;}希望大家多多点赞哦~~