侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【DFS】小猫爬山

GabrielxD
2023-03-01 / 0 评论 / 0 点赞 / 122 阅读 / 1,052 字
温馨提示:
本文最后更新于 2023-03-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

165. 小猫爬山 - AcWing题库


翰翰和达达饲养了 NN 只小猫,这天,小猫们要去爬山。

经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 WW ,而 NN 只小猫的重量分别是 C1C2CNC_1、C_2……C_N

当然,每辆缆车上的小猫的重量之和不能超过 WW

每租用一辆缆车,翰翰和达达就要付 11 美元,所以他们想知道,最少需要付多少美元才能把这 NN 只小猫都运送下山?

输入格式

11 行:包含两个用空格隔开的整数, NNWW

2..N+12..N+1 行:每行一个整数,其中第 i+1i+1 行的整数表示第 ii 只小猫的重量 CiC_i

输出格式

输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。

数据范围

1N181 \le N \le 18 ,
1CiW1081 \le C_i \le W \le 10^8

输入样例:

5 1996
1
2
1994
12
29

输出样例:

2

解题

方法一:DFS 回溯 剪枝

思路

首先根据本题的数据范围(1N181 \le N \le 18)可以基本判断出本题应该用DFS+剪枝求解。

具体来说:从前向后枚举每一只小猫,对于每一只小猫,枚举把它放在哪一辆车内。搜索树如下( cat=0n1cat = 0 \dots n-1 ):

image-20230301182854323

暴搜:dfs(car,cat)dfs(car, cat)carcar 表示当前有多少辆车, catcat 表示当前尝试枚举到的小猫下标):

  • 出口:当 catcat 枚举越界( catncat \ge n )时,更新最少所需要车的数量,退出程序。
  • 枚举第 0car10 \dots car-1 辆车:
    • 如果把猫 catcat 放在当前这辆车上没有超载:
      • 尝试放上去,递归下一只猫( dfs(car,cat+1)dfs(car, cat + 1) )。
      • 回溯(还原当前车的重量)。
  • 开一辆新车放猫,递归下一只猫( dfs(car+1,cat+1)dfs(car + 1, cat + 1) )。
  • 回溯(删掉新车)。

剪枝:

  1. 优化搜索顺序:体重较重的猫有更大可能占满一辆车,这可以让之后尽可能少的猫选择放在该车上,所以可以有效地减少搜索的分支,所以应该尽可能优先枚举体重较重的猫(把猫按体重降序排序)。
  2. 可行性剪枝:如果当前猫放在某辆车上重量超过了 WW,就应该直接剪枝。
  3. 最优性剪枝:如果当前车的数量已经大于等于维护的最优解的车的数量了,就应该直接剪枝。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, w;
    static Integer[] cats; // 基础类型数组不能直接排序 所以用包装类数组
    static int[] cars; // 维护每辆车当前的的总重量
    static int ans = 20;
    
    static void dfs(int car, int cat) {
        if (car >= ans) return; // 最优性剪枝
        if (cat == n) {
            ans = car; // 更新最优方案
            return;
        }
        int curr = cats[cat];
        for (int i = 0; i < car; ++i) {
            if (cars[i] + curr <= w) { // 可行性剪枝
                cars[i] += curr;
                dfs(car, cat + 1);
                cars[i] -= curr;
            }
        }
        cars[car] = curr;
        dfs(car + 1, cat + 1);
        cars[car] = 0;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        w = (int) in.nval;
        cats = new Integer[n];
        cars = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            cats[i] = (int) in.nval;
        }
        Arrays.sort(cats, Comparator.reverseOrder()); // 优化搜索顺序
        dfs(0, 0);
        System.out.println(ans);
    }
}
0

评论区