本题的搜索顺序是:(1)新元素放入当前已有的某个组中;(2)创建新组,并将新元素放入该组。
在分析清楚搜索的顺序之后,还需进行剪枝。用ans
表示当前的最优解,用cnt
表示当前已分的组的数量,则剪枝的方法是:
- 当
cnt >= ans
时,直接return
;
继续往下搜索得到的结果不可能优于当前的ans
。 - 优先考虑决策少的元素(DFS常用的优化方法,需理解并掌握);
在本题的场景下,体重越大的猫,可能的决策就越少,原因是:上述的决策(2)对于所有的猫都是一样的,但对于决策(1),体重越重的猫加入到某个组时越有可能导致超重,可能的决策就会少一些。
import java.util.*;
public class Main{
static int N = 20, n, w;
static Integer[] cat = new Integer[N];
static int[] sum = new int[N];
static int ans = N;
public static void dfs(int u, int cnt){
if(cnt >= ans) return;
if(u == n){
ans = cnt;
return;
}
// 放入当前已有的组中
for(int i = 0; i < cnt; i ++){
if(cat[u] + sum[i] <= w){
sum[i] += cat[u];
dfs(u + 1, cnt);
sum[i] -= cat[u];
}
}
// 创建新组,放入此新组中
sum[cnt] += cat[u];
dfs(u + 1, cnt + 1);
sum[cnt] -= cat[u];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
w = sc.nextInt();
for(int i = 0; i < n; i ++) cat[i] = sc.nextInt();
// 从大到小排序
Arrays.sort(cat, 0, n, (o1, o2) -> Integer.compare(o2, o1));
// dfs
dfs(0, 0);
System.out.println(ans);
}
}