原题链接

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猫能不能放在之前的车中)

  • for循环,枚举第一辆车到现在所有的车

  • 如果可以放得下u猫，则进入新的dfs（u+1,k）

  • (u+1,k),

可以放得下猫所以车辆数不变,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;
}