设计一个商务网站,wordpress最新文章,网站建设毕业实习报告,免费网站电视剧下载165. 小猫爬山 - AcWing题库
翰翰和达达饲养了 N 只小猫#xff0c;这天#xff0c;小猫们要去爬山。
经历了千辛万苦#xff0c;小猫们终于爬上了山顶#xff0c;但是疲倦的它们再也不想徒步走下山了#xff08;呜咕_#xff09;。
翰翰和达达只好花钱让它们…165. 小猫爬山 - AcWing题库
翰翰和达达饲养了 N 只小猫这天小猫们要去爬山。
经历了千辛万苦小猫们终于爬上了山顶但是疲倦的它们再也不想徒步走下山了呜咕_。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W而 N 只小猫的重量分别是 C1、C2……Cn。
当然每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车翰翰和达达就要付 1 美元所以他们想知道最少需要付多少美元才能把这 N 只小猫都运送下山
输入格式
第 1 行包含两个用空格隔开的整数N 和 W。
第 2..N1 行每行一个整数其中第 i1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数表示最少需要多少美元也就是最少需要多少辆缆车。
数据范围
1≤N≤18 1≤Ci≤W≤108
输入样例
5 1996
1
2
1994
12
29输出样例
2
解析
DFS之剪枝与优化主要方法:
1.优化搜索顺序大部分情况下我们应该优先搜索分支较少的节点 2.排除等效冗余 3.可行性剪枝 4.最优性剪枝 5.记忆化搜索dp)
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
using namespace std;
typedef long long LL;
const int N 20;
int n, w;
int cr[N], sum[N];
int ans;int cmp(const int a, const int b) {return a b;
}void dfs(int u, int k) {//最优性剪枝if (k ans)return;if (u n) {ans k;return;}for (int i 1; i k; i) {if (sum[i] cr[u] w) {//可行性剪枝sum[i] cr[u];dfs(u 1, k);sum[i] - cr[u];//恢复现场}}sum[k 1] cr[u];dfs(u 1, k 1);
}int main() {cin n w;for (int i 1; i n; i) {scanf(%d, cr[i]);}//优化搜索顺序sort(cr 1, cr 1 n, cmp);ans n;dfs(1, 1);cout ans endl;return 0;
}
