第15章 搜索枚举

1、文具店

算法分析

暴力枚举每种情况，dfs(u,cnt)表示从第0个位置开始枚举，当前选第0个，当 cnt == k 且 u == n时，表示已经枚举完了所有位置且已经够k个，则更新ans
当枚举到第u个位置，准备枚举第cnt个数的时候，若后面的总元素小于剩下需要的个数时，则剪枝

时间复杂度

有剪枝，会比这个复杂度小很多

Java代码

import java.util.Scanner;

public class Main {
    static int n,k;
    static String s;
    static String[] g = new String[10];
    static int ans = Integer.MAX_VALUE;
    static void dfs(int u,int cnt)
    {
        //可行性剪枝
        if(n - u + 1 < k - cnt - 1) return ;
        if(cnt == k && u == n)
        {
            int res = 0;
            for(int i = 0;i < k;i ++) res += Integer.parseInt(g[i]);
            ans = Math.min(ans, res);
            return;
        }
        for(int i = u + 1;i <= n;i ++)
        {
            g[cnt] = s.substring(u,i);
            dfs(i,cnt + 1);
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        s = scan.next();
        n = s.length();
        k = scan.nextInt();
        dfs(0,0);
        System.out.println(ans);
    }
}

2、超级书架2

算法分析

暴力枚举所有奶牛，每个奶牛有选和不选两种情况

时间复杂度

Java代码

import java.util.Scanner;

public class Main {
    static int N = 25;
    static int n,high;
    static int[] h = new int[N];
    static int ans = Integer.MAX_VALUE;
    static void dfs(int u,int cnt)
    {
        if(u == n)
        {
            if(cnt >= high) ans = Math.min(ans, cnt);
            return;
        }
        //不选
        dfs(u + 1,cnt);
        //选
        dfs(u + 1,cnt + h[u]);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        high = scan.nextInt();
        for(int i = 0;i < n;i ++) h[i] = scan.nextInt();
        dfs(0,0);
        System.out.println(ans - high);
    }
}

3、自然数拆分

算法分析

依次枚举所有小于n的数，若枚举的数的和等于n则输出，大于n则break
dfs(u,x,num):u表示枚举第u个数，x表示从x开始往后枚举，num表示当前已经枚举的数的总和

时间复杂度

存在剪枝，时间复杂度远小于上面的

Java代码

import java.util.Scanner;

public class Main {
    static int N = 25;
    static int n;
    static int[] a = new int[N];
    static void dfs(int u,int x,int num)
    {
        if(num > n) return;
        if(num == n) 
        {
            System.out.print(n + "=");
            for(int i = 0;i < u;i ++)
            {
                if(i != u - 1) System.out.print(a[i] + "+");
                else System.out.println(a[i]);
            }
            return;
        }
        for(int i = x;i < n;i ++)
        {
            a[u] = i;
            dfs(u + 1,i,num + i);
            
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs(0,1,0);
    }
}

4、狂暴石

算法分析

每块狂暴石有选和不选两种情况，记录当前愤怒值的乘积numa，暴躁值的累加numb，需要对所有情况都不选进行特判即numa == 1 && numb == 0

时间复杂度

Java代码

import java.util.Scanner;

public class Main {
    static int N = 15;
    static int n;
    static int[] a = new int[N];//愤怒值
    static int[] b = new int[N];//暴躁值
    static long ans = Long.MAX_VALUE;
    static void dfs(int u,int numa,int numb)
    {
        if(u == n)
        {
            if(numa == 1 && numb == 0) return;//可行性剪枝
            ans = Math.min(ans, Math.abs(numa - numb));
            return;
        }
        //不选
        dfs(u + 1,numa,numb);
        //选
        dfs(u + 1,numa * a[u],numb + b[u]);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 0;i < n;i ++)
        {
            int x = scan.nextInt();
            int y = scan.nextInt();
            a[i] = x;
            b[i] = y;
        }
        dfs(0,1,0);
        System.out.println(ans);
    }
}