原题链接
https://www.acwing.com/problem/content/description/167/
思路
想法
1.排序优化 //可略过,不加也可以ac
2.让猫坐满一辆车
3.开新的车
4.重复2-3
具体代码思路(2-3步骤)
1.确定参数 (int u(第几只猫),int k(第几辆车))
2.跳出条件 (u==n) 当猫走完时,跳出,n为总得猫数量,已经枚举完最后一个猫了。所以跳出,为什么是u==n,因为数组是从0开始的,最后一个猫为n-1。
3.判断当前这只猫,简称u猫(判断u猫能不能放在之前的车中)
可以放得下猫所以车辆数不变,k就不变,u猫被放进去了,下一只猫就是u+1猫。
1 2 3 4 5 6 7 8 9 10
| for(int i=0;i<k;i++) //从第一辆车开始遍历,遍历到k辆车,如果可以塞下第u只猫则执行; { if(a[u]+car[i]<=w) { car[i]+=a[u]; dfs(u+1,k); car[i]-=a[u]; } }
|
- 如果放不下猫,则开一辆新车dfs(u+1,k+1)
dfs(下一只猫,下一辆车)
1 2 3 4
| car[k]=a[u]; dfs(u+1,k+1); car[k]=0;
|
- 这里回溯为什么是car[k]=0,因为没放猫时,车的重量是0
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| #include <bits/stdc++.h>
using namespace std;
int n,w,ans=20; int a[20],car[20];
int cmp(int a,int b) //从大到小 函数sort第三个参数 { return a>b; }
void dfs(int u,int k) { if(k>=ans) return; //注意等于ans可以减少时间,不加等于号800多ms,加了20多ms if(u==n) //u个猫等于n个猫,猫坐完车的时候 { ans=k; return; } //-----------------------------------start for(int i=0;i<k;i++) //从第一辆车开始遍历,遍历到k辆车,如果可以塞下第u只猫则执行; { if(a[u]+car[i]<=w) { car[i]+=a[u]; dfs(u+1,k); car[i]-=a[u]; } } //-------------------------------------end //开新车 car[k]=a[u]; dfs(u+1,k+1); car[k]=0;
}
int main() { //---------输入---------- scanf("%d%d",&n,&w); for(int i=0;i<n;i++) scanf("%d",&a[i]); //---------排序优化---------- sort(a,a+n,cmp); //--------------------------------- dfs(0,0);
printf("%d",ans); return 0; }
|