题目描述
翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为W，而N只小猫的重量分别是$C_1、C_2……C_N$。
当然，每辆缆车上的小猫的重量之和不能超过W。
每租用一辆缆车，翰翰和达达就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
输入格式
第1行：包含两个用空格隔开的整数，N和W。
第2..N+1行：每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
$1≤N≤18$
$1≤C_i≤W≤108$
样例
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2
搜索
这道题目我们肯定是搜索了,我们发现这道题目有两个可以剪枝的部分,一个是如果当前的答案已经大于了我们已知的最小答案,不用说直接return返回即可.第二个剪枝则是,我们可以将小猫的体重从大到小排序,这样我们的搜索树就会缩短许多,至于为什么,因为我们的剩余空间就变小了,然后可选择的猫也就少了.
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=20;
long long ans=1e7,a[N],p[N];
int n,m;
int cmp(long long a,long long b)
{
return a>b;
}
void dfs(long long x,long long cnt)
{
if (cnt>=ans)//剪枝1
return ;
if (x==n+1)
{
ans=min(ans,cnt);
return ;
}
for(int i=1;i<=cnt;i++)//枚举当前每一辆新车
if (p[i]+a[x]<=m)//如果这辆车装得下这只小猫的话
{
p[i]+=a[x];
dfs(x+1,cnt);
p[i]-=a[x];
}
p[cnt+1]=a[x];//开新车
dfs(x+1,cnt+1);
p[cnt+1]=0;//回溯
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n,cmp);//小猫体重排序
dfs(1,0);
cout<<ans;
return 0;
}
请问为什么把dfs最后一句话删掉，结果仍然正确。。。。。
因为这是最后一句话，回溯后的cnt是小于当前状态的，后面的操作这个数组之前都会先赋初值，盖掉这个操作
谢谢你问到了我想要的问题，所以这一步就是出栈对吗？
没有排序也过了
但编译时间没有排序短
if (cnt>=ans)//剪枝1
return ;
这咋理解，为啥没有这个答案错误。
这里是最优化剪枝，没有这条会超时
大佬能问一下为什么不用像上一题分成互质组那样加一个bool变量标记是否可以放下，默认为true，如果有一个车能放下就改成false；如果都放不下默认为true的话就去新开一辆车。为什么就直接把开新车放到下面了呢
同问
最优解可能存在于新开一辆车中，要枚举到所有的可行性解
嗷确实 有道理 谢谢好兄弟
试过了然后TLE了
cnt=N为什么不行 不能等于猫的数量吗
为什么dfs中枚举车时i从1开始啊,可是主函数中是从0开始的啊？
注意他是1到<=cnt一样的。
请问为什么要p[i]-=a[x];和 p[cnt+1]=0;呢？
dfs需要恢复原来的状态，这样的话才能正确进行下一次搜索
大佬能不能解释一下为什么优化搜索顺序有效？理论上来说不管什么顺序最后每一个节点都会被搜过啊？
如果没有最优性剪枝应该是遍历状态空间的，但是有了当前答案大于已知答案就返回的最优性剪枝搜索顺序就比较有用了，因为我预先得到的答案比较小，那么我之后的答案可以直接返回。
大佬，能不能给讲一下 p[cnt+1]回溯 这句代码，不是很明白。
当前有cnt台缆车,然后我们现在这只小猫没有缆车做了,所以我们要cnt+1,那么这台新车就有a[x]的空间被这只小猫占据了.
请问这个时间复杂度怎么算？
一般来说搜索题目，加了剪枝，时间复杂度无法计算，因为这个剪枝按照数据范围，会大幅度优化。
为啥不能贪心，尽量装大的
贪心了,我们排序就是让大的先入.
e 我开始想错了
肯定是要搜索的
不用搜索，直接贪心好像基本都能过，除了最后一个测试用例。贪心怎么改都不行好像，搞不懂为什么一定得搜索。
附一下代码：
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
bool cmp(int a, int b) {
return a > b;
}
int main() {
int N, W;
int arr[20];
scanf(“%d %d”, &N, &W);
for (int i = 0; i < N; i++) {
scanf(“%d”, &arr[i]);
}
sort(arr, arr + N, cmp);
}
请问一下，为什么不再开一个数组用来标记猫是否已经进了车呢？
理解的不是很清楚。。
因为这里我们是枚举车,而不是小猫,而且x是小猫代号,你会发现x是不会相同的,除非方案不一样.
明白了，感谢！！