蓝桥杯省赛真题

准备蓝桥杯时候刷真题的一小部分记录，有几道题在我之前发过的 蓝桥杯普及题 中，好多复杂的题直接把思路写在代码注释上，也没精力再整理到这了，后来还整理了一部分国赛真题，放在 OneNote 上的，结果在整理 OneDrive 上的文件时一不小心（手贱）给送走了，蓝桥杯的相关题刷过的还蛮丰富的，但记录下来的就只有这些了

2018 年

三角形的面积

题目：
已知三角形三个顶点在直角坐标系下的坐标分别为：

(2.3, 2.5)

(6.4, 3.1)
(5.1, 7.2)

求该三角形的面积。
注意，要提交的是一个小数形式表示的浮点数。
要求精确到小数后 3 位，如不足 3 位，需要补零。

思路：
可以采用两种算法：图形切割和海伦公式

• 图形切割法：用最外侧两点的坐标减去最靠近圆心坐标的点求出两个正方形的边长，用大正方形的面积减去小正方形的面积就是三角形的两倍
• 海伦公式：$S=\sqrt{P(P-a)(P-b)(P-c)}$，其中 P 是周长的一半，先根据坐标用勾股定理求出每条边的边长

代码：

public static void main(String[] args) {
    // 图形切割法
    // 用最外侧两点的坐标减去最靠近圆心坐标的点求出两个正方形的边长
    // 用大正方形的面积减去小正方形的面积就是三角形的两倍
    double x1 = 2.3;
    double y1 = 2.5;
    double x2 = 6.4;
    double y2 = 3.1;
    double x3 = 5.1;
    double y3 = 7.2;
    double X1 = x2 - x1;
    double Y1 = y2 - y1;
    double X2 = x3 - x1;
    double Y2 = y3 - y1;
    System.out.println((X1 * Y2 - X2 * Y1) / 2);
    // 海伦公式
    // 面积 =sqrt(P(P-a)(P-b)(P-c))；其中 P 是周长的一半
    // 先根据坐标用勾股定理求出每条边的边长
    double a = Math.sqrt((6.4 - 2.3) * (6.4 - 2.3) + (3.1 - 2.5) * (3.1 - 2.5));
    double b = Math.sqrt((5.1 - 2.3) * (5.1 - 2.3) + (7.2 - 2.5) * (7.2 - 2.5));
    double c = Math.sqrt((6.4 - 5.1) * (6.4 - 5.1) + (7.2 - 3.1) * (7.2 - 3.1));
    double p = (a + b + c) / 2;
    System.out.println(Math.sqrt(p * (p - a) * (p - b) * (p - c)));
}

最大乘积

题目：
把 1~9 位数字分成两组，将其相乘，使得它的乘积也是不重复的九个数字

984672 * 351=345619872

9 * 87146325=784316925

符合这种规律的乘式还有很多，求乘积最大的那一个

思路：

1. 首先进行全排列，这样就不用考虑重复的问题
2. 将每次全排列的 9 个数字进行拆分相乘，保留符合条件的乘积，最后输出最大值即可

代码：

public class MaxProduct {
    static int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    static int ans = 0;

    public static void main(String[] args) {
        dfs(0);
        System.out.println(ans);
    }

    static void dfs(int m) {
        if (m >= 9) {// 穷举所有全排列的将其分割相乘，判断乘积是否符合条件
            for (int i = 1; i <= 8; i++) {
                int x = 0, y = 0;
                for (int j = 0; j < i; j++)
                    x = 10 * x + a[j];// 定义左边的乘数
                for (int k = i; k < 9; k++)
                    y = 10 * y + a[k];// 定义右边的乘数

                int res = x * y;
                int[] cnt = new int[10];
                while (res > 0) {
                    cnt[res % 10]++;// 将乘积分开放到数组中，对应下标的数组设为 1
                    res /= 10;
                }
                boolean flag = true;
                for (int k = 1; k <= 9; k++)
                    if (cnt[k] != 1) {
                        flag = false;
                        break;
                    }

                if (flag) {
                    ans = Math.max(x * y, ans);// 将最大的乘积保存下来
                    if (x * y == ans)
                        System.out.println(x + " * " + y + " == " + ans);
                }
            }
            return;
        }

        for (int i = m; i < 9; i++) {
            swap(i, m);
            dfs(m + 1);
            swap(i, m);
        }

    }

    static void swap(int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

整理玩具

题目：
小明有一套玩具，一共包含 NxM 个部件。这些部件摆放在一个包含 NxM 个小格子的玩具盒中，每个小格子中恰好摆放一个部件。
每一个部件上标记有一个 0~9 的整数，有可能有多个部件标记相同的整数。
小明对玩具的摆放有特殊的要求：标记相同整数的部件必须摆在一起，组成一个矩形形状。
如以下摆放是满足要求的：

00022

00033
44444

12244

12244
12233

01234

56789

以下摆放不满足要求：

11122

11122
33311

111111

122221
111111

11122

11113
33333

输入
输入包含多组数据。
第一行包含一个整数 T，代表数据组数。 (1 <= T <= 10)
以下包含 T 组数据。
每组数据第一行包含两个整数 N 和 M。 (1 <= N, M <= 10)
以下包含 N 行 M 列的矩阵，代表摆放方式。
输出
对于每组数据，输出 YES 或者 NO 代表是否符合小明的要求。
【样例输入】

3

3 5
00022
00033
44444
3 5
11122
33311
2 5
01234
56789

【样例输出】

YES

NO
YES

思路：

1. 将数组中的数放到 HashSet 中去重，仅记录玩具的种类
2. 构造方法，用 Set 中的每一个值去判断，返回 Boolean 型
   • 记录当前数据从左上到右下的坐标点，然后再遍历矩阵范围内的所有数字是否相同即可
   • 判断方法可以把矩阵中的所有数字相加，然后根据矩阵下标求出个数，判断 sum==count*num 的值即可
3. 输入的数组没有空格，可以采用 toCharArray() 将其作为字符串存为字符数组，（Char 和 int 的自动转换）

代码：

public class TidyupToys {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();// 输入组数
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            HashSet<Character> set = new HashSet<>();// 存放出现的数字（不重复）
            char[][] arr = new char[n][m];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.next().toCharArray();// 输入数组（按行输入）
            }
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    set.add(arr[i][j]);
                }
            }
            boolean flag = true;
            for (Character c : set) {// 判断每一个不同的数据（从左上往右下进行寻找）
                if (!find(arr, c)) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                System.out.println("YES");
            else
                System.out.println("NO");

        }
    }

    // 从左上角向右下角寻找，因为数据比较小，每个数字找到他第一次出现 (x1,y1) 和
    // 最后出现的（x2,y2）, 然后遍历再 x1 x2 y1 y2 范围的数，如果符合是矩形
    // 那么遍历的每一个数一定是相同的，如果不相同说明不符合条件。
    static boolean find(char[][] arr, char res) {
        int minx = 0;
        int miny = 0;
        int maxx = 0;
        int maxy = 0;
        int temp = 0;
        boolean flag = true;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == res) {// 寻找 set 中的字符在数组中的第一次出现
                    if (temp == 0) {
                        minx = i;
                        miny = j;
                    }
                    temp++;
                    maxx = Math.max(i, maxx);
                    maxy = Math.max(j, maxy);// 找出它的左上点和右下点下标
                }
            }
        }
        int sum = 0;
        if (maxx == minx && miny == maxy) {
            return true;// 只出现了一次必然不会出错
        }
        int count = (maxx - minx + 1) * (1 + maxy - miny);// 记录应该出现的个数
        // 在判断的时候每个数的大小 * 个数，看是否等于遍历和。
        for (int i = minx; i <= maxx; i++) {
            for (int j = miny; j <= maxy; j++) {
                sum += arr[i][j];
            }
        }
        if (sum != res * count) {
            flag = false;
        }
        return flag;
    }
}

版本分支

题目：
公司一个奇怪的项目。这个项目的代码一直在不断分支 (branch) 但是从未发生过合并 (merge)。
现在这个项目的代码一共有 N 个版本，编号 1~N，其中 1 号版本是最初的版本。
除了 1 号版本之外，其他版本的代码都恰好有一个直接的父版本；即这 N 个版本形成了一棵以 1 为根的树形结构。
如下图就是一个可能的版本树：

graph TB
    1-->2;
    1-->3;
    2-->5;
    3-->4;
    3-->6;

现在小明需要经常检查版本 x 是不是版本 y 的祖先版本。你能帮助小明吗？

输入
第一行包含两个整数 N 和 Q，代表版本总数和查询总数。
以下 N-1 行，每行包含 2 个整数 u 和 v，代表版本 u 是版本 v 的直接父版本。
再之后 Q 行，每行包含 2 个整数 x 和 y，代表询问版本 x 是不是版本 y 的祖先版本。
输出
对于每个询问，输出 YES 或 NO 代表 x 是否是 y 的祖先。
【样例输入】

6 5

1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4

【样例输出】

YES

YES
NO

思路：

1. 按数组进行关系的存放，每个版本下标中存放它的直接父节点
2. 如果在判断时 arr[y]==x, 那就是对应的直接父节点，如果不是就将它的 arr[y] 的值取出继续向上查找，一直到源点 1 结束

代码：

public class VersionBranching {
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        arr = new int[N + 1];// 数组从 1 开始
        for (int i = 1; i <= N; i++) {
            arr[i] = i;
        }
        for (int i = 1; i < N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            union(x, y);
        }
        for (int i = 0; i < Q; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (find(x, y)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }

    // 寻找父节点
    private static boolean find(int x, int y) {
        if (arr[y] == x)// 是直接父节点
            return true;
        int t = arr[y];
        while (t != 1) {// 没到源点，一直往上寻找
            t = arr[t];
            if (t == x)
                return true;
        }
        return false;
    }

    private static void union(int x, int y) {
        if (arr[y] == y) {
            arr[y] = x;
        }
    }
}

2017 年

平方十位数

题目：
由 0~9 这 10 个数字不重复、不遗漏，可以组成很多 10 位数字。
这其中也有很多恰好是平方数（是某个数的平方）。
比如：1026753849，就是其中最小的一个平方数。
请你找出其中最大的一个平方数是多少？

思路：

1. 因为十位数的每位各不重复，所以可以采用 DFS 全排列，然后更改递归出口
2. 递归出口的判断条件有十位数和平方数两个

代码：

public class SquareTen {
    static int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};// 因为求最大值，反向第一
    static int ans = 0;// 平方数的个数

    public static void main(String[] args) {
        dfs(0);
        System.out.println(ans);
    }

    static void dfs(int m) {// 用 dfs 全排列枚举
        if (m >= 10) {// 将递归出口定义为平方数
            long res = 0;
            for (int i = 0; i < 10; i++)
                res = 10 * res + arr[i];
            long r = (long) Math.sqrt(res);
            if (("" + res).length() != 10)// 前边加空格转换为字符串判断长度
                return;
            if (r * r == res) {// 是平方数
                ans++;
                System.out.println(res);
            }
            return;
        }

        for (int i = m; i < 10; i++) {// 全排列公式
            swap(i, m);
            dfs(m + 1);
            swap(i, m);
        }
    }

    static void swap(int a, int b) {// 交换方法
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}

填字母游戏

题目：
K 大师在纸上画了一行 n 个格子，要小明和他交替往其中填入字母。

1. 轮到某人填的时候，只能在某个空格中填入 L 或 O
2. 谁先让字母组成了“LOL”的字样，谁获胜。
3. 如果所有格子都填满了，仍无法组成 LOL，则平局。

本题的输入格式为：
第一行，数字 n（n<10），表示下面有 n 个初始局面。
接下来，n 行，每行一个串，表示开始的局面。
比如： ****** , 表示有 6 个空格。 L**** , 表示左边是一个字母 L，它的右边是 4 个空格。

要求输出 n 个数字，表示对每个局面，如果小明先填，当 K 大师总是用最强着法的时候，小明的最好结果。
1 表示能赢
-1 表示必输
0 表示可以逼平

输入

4

***

L**L

L**L***L

L*****L

输出

0

-1
1

思路：

1. 判断方法，首先判断是否拿到时就出现 "LOL"，如果有说明已经输了（此判断还会在递归中判断是否填写成功）
2. 第二次判断是否还有’*' 存在，若没有就是平局
3. 然后模拟填数，将原本的’*' 赋值为’L’或者’O’然后递归到方法中判断

代码：

public class FillLetters {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            char[] a = sc.next().toCharArray();// 将字符串转换为字符数组存放
            System.out.println(find(a));
        }
    }

    static int find(char[] a) {
        String s = new String(a);// 将数组转换为字符串方便查找
        if (s.contains("LOL"))// 当拿到时就有了 "LOL" 直接失败，或者模拟填写时成功填写
            return -1;
        if (!s.contains("*"))// 没有填写位置也没返回 LOL 说明平局
            return 0;
        int n = a.length;// 构建循环模拟填写过程
        int dogfall = 0;// 平局记录
        for (int i = 0; i < n; i++) {
            if (a[i] == '*') {// 如果当前是空格可以填写，进行模拟
                try {// 可能出现异常
                    a[i] = 'L';// 填入 L
                    if (find(a) == -1)// 拿到时出现 LOL
                        return 1;
                    else if (find(a) == 0)
                        dogfall = 1;
                    a[i] = 'O';// 填入 O
                    if (find(a) == -1)// 拿到时出现 LOL
                        return 1;
                    else if (find(a) == 0)
                        dogfall = 1;
                } finally {// 无视异常与否进行执行
                    a[i] = '*';
                }
            }

        }
        if (dogfall == 1)// 填写中平局
            return 0;
        return -1;// 没在填数过程中返回 1 则必返回 0
    }
}

2016 年

愤怒小鸟

题目：
两辆相对的火车（A、B）以 10/ 秒的速度行驶，初始相距 1000，中间有一只小鸟以时速 50/ 秒的速度进行折返飞行（首先从 A 飞向 B）
最后两辆车在相距 1 的位置停下，求这期间小鸟撞到 B 车多少次

思路：

1. 利用距离与速度推导出相遇的时间，然后计数器加一，再用时间更新位置
2. 中间用 flag 变量的正负值确定方向

代码：

public class AngryBirds {
    public static void main(String[] args) {
        double l = 0;//A
        double r = 1000;//B
        int count = 0;// 计数
        double b = 0;// 小鸟
        int flag = 1;// 用来判断飞向那个火车
        double t;// 记录时间
        while (r - l > 1) {// 两车未停
            if (flag == 1) {// 从 A 向 B 飞
                t = (r - b) / 60.0;// 鸟和 B 火车相遇所用的时间
                count++;// 只有和 B 相遇的时候才计数加
                l += 10.0 * t;// 更新 A 这段时间走的
                r -= 10.0 * t;// 更新 B
                b += 50.0 * t;// 更新鸟的位置
                flag = -1;// 下次应该向 A 走
            } else {// 向火车 A 走
                t = (b - l) / 60.0;
                l += 10.0 * t;
                r -= 10.0 * t;
                b -= 50.0 * t;
                flag = 1;
            }
        }
        System.out.println(count);
    }
}

反幻方

题目：
将 1~9 填入九宫格，求每行每列和两个对角线上的值的和互不相等的情况
旋转镜像算一种

思路：

1. 全排列代码，将递归出口改为题意
2. 旋转看边，镜像一般为 2

代码：

public class Permutation {
    static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    static int ans = 0;

    public static void main(String[] args) {
        dfs(0);
        System.out.println(ans/8);// 旋转看边数，镜像一般为 2
    }

    static void dfs(int m) {
        if (m >= 9) {// 一次排列完成，进行判断
            int a=arr[0]+arr[1]+arr[2];
            int b=arr[3]+arr[4]+arr[5];
            int c=arr[6]+arr[7]+arr[8];
            int x=arr[0]+arr[3]+arr[6];
            int y=arr[1]+arr[4]+arr[7];
            int z=arr[2]+arr[5]+arr[8];
            int i=arr[0]+arr[4]+arr[8];
            int j=arr[2]+arr[4]+arr[6];
            if (a==b||a==c||a==x||a==y||a==z||a==i||a==j)
                return;
            if (b==c||b==x||b==y||b==z||b==i||b==j)
                return;
            if (c==x||c==y||c==z||c==i||c==j)
                return;
            if (x==y||x==z||x==i||x==j)
                return;
            if (y==z||y==i||y==j)
                return;
            if (z==i||z==j)
                return;
            if (i==j)
                return;
            ans++;
        }
        for (int i = m; i < arr.length; i++) {
            int t = arr[i];
            arr[i] = arr[m];
            arr[m] = t;
            dfs(m + 1);
            t = arr[i];
            arr[i] = arr[m];
            arr[m] = t;
        }
    }
}

路径之谜

题目：
假设城堡地面是 n x n 个方格。
从西北角走到东南角，可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭（西和北各有 n 个靶子）
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断行走路线吗？
有时是可以的，比如图中的例子。
已知箭靶数字，求行走路径（测试数据保证路径唯一）

输入
第一行一个整数 N(0<N<20)，表示地面有 N x N 个方格
第二行 N 个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行 N 个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出
一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号：0, 1, 2, 3…
比如，图中的方块编号为：

0 1 2 3

4 5 6 7
8 9 10 11
12 13 14 15

样例输入

4

2 4 3 4
4 3 3 3

样例输出

0 4 5 1 2 3 7 11 10 9 13 14 15

思路：

1. 要想走相同的路线，可以设置为每走一步，拔掉北边和西边靶子上的箭，这样最后所以的靶子都清零，就表示路径是相同的
2. 使用 DFS 搜索
3. 需注意几点
   • 入口（0，0）为必经点，在放入方法时就要拔掉对应的箭
   • 路线不能重复，定义 flag 数组进行记录
   • 得到的结果放入 ArrayList 集合中便于模拟失败后删除

代码：

public class MysteryPath {
    static int n;// 记录格数 n*n
    static int[] west;// 西边的靶子
    static int[] north;// 北边的靶子
    static boolean[][] flag;// 标记是否走过
    static int[] dx = new int[]{1, 0, -1, 0};// 记录行走的方式
    static int[] dy = new int[]{0, 1, 0, -1};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        west = new int[n];
        north = new int[n];
        flag = new boolean[n][n];
        for (int i = 0; i < n; i++)
            north[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            west[i] = in.nextInt();
        west[0]--;// 左上角的方格为入口，必经
        north[0]--;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        flag[0][0] = true;
        dfs(0, 0, list);

    }

    static void dfs(int x, int y, ArrayList<Integer> list) {
        if (x == n - 1 && y == n - 1) {// 到达右下的方格
            for (int i = 0; i < n; i++)
                if (west[i] > 0 || north[i] > 0)// 模拟的路径若是相同所有的的靶子应该归零
                    return;
            //System.out.println("!"+c[i]+" "+r[i]);

            for (Integer integer : list) //==for (int i = 0; i < list.size(); i++)// 符合条件将放入集合的路径变量读取出来
                System.out.print(integer + " ");
            System.out.println();
            return;
        }

        for (int i = 0; i < 4; i++) {// 四个方向
            int row = x + dx[i];// 走出之后的行
            int colum = y + dy[i];// 走出之后的列
            if (row >= 0 && row < n && colum >= 0 && colum < n && !flag[row][colum] && west[row] > 0 && north[colum] > 0) {
                // 不能越界；不能重复；不能是没射过箭的
                west[row]--;// 按原路走拔掉每一行的箭
                north[colum]--;
                list.add(row * n + colum);// 行号 * N+ 列号就是方格的下标，放入集合中
                flag[row][colum] = true;// 标记走过
                dfs(row, colum, list);// 继续下一步
                //Reset in trace
                flag[row][colum] = false;
                list.remove(list.size() - 1);
                west[row]++;
                north[colum]++;
            }
        }
    }
}

2015 年

分机号

题目：
有一种三位数的号码，符合以下两种条件：
降序排列且每位都不重复
如符合条件的：732；641；520
不符合条件的：660；123；201

思路：

1. 三重循环嵌套进行枚举
2. 第一层循环的变量从 1 开始，三位数的百位不能为零
3. 降序且重复可以用 i > j && i > k && j > k 进行判断

代码：

public static void main(String[] args) {
    long ans = 0;
    for (int i = 1; i < 10; i++) {// 百位不为零
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 10; k++) {
                if (i > j && i > k && j > k) {// 定义降序且不重复条件
                    ans++;
                    System.out.println("" + i + j + k);
                }
            }
        }
    }
    System.out.println(ans);
}

五星填数

题目：
五星图案节点填上数字：1~12，除去 7 和 11。
要求每条直线上数字和相等。
请你利用计算机搜索所有可能的填法有多少种。
注意：旋转或镜像后相同的算同一种填法。

思路：

1. 将 1~12 进行全排列，五个一组按照相应的下标相加，符合条件 ans++
2. 其中有 5 种旋转，2 种镜像，所以最后的结果 ans/10
3. dfs 中的循环变量，要从 dfs 变量开始，否则越界

代码：

public class FiveStars {
    static int[] arr = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12};
    static int ans = 0;

    public static void main(String[] args) {
        dfs(0);
        System.out.println(ans / 10);// 最后的结果去掉旋转和镜像 5*2
    }

    static void dfs(int m) {
        if (m == 10) {// 完成一次全排列
            if (arr[1] + arr[2] + arr[3] + arr[4] != arr[0] + arr[2] + arr[5] + arr[8])
                return;
            if (arr[1] + arr[2] + arr[3] + arr[4] != arr[0] + arr[3] + arr[6] + arr[9])
                return;
            if (arr[1] + arr[2] + arr[3] + arr[4] != arr[1] + arr[5] + arr[7] + arr[9])
                return;
            if (arr[1] + arr[2] + arr[3] + arr[4] != arr[4] + arr[6] + arr[7] + arr[8])
                return;
            ans++;// 符合就答案加一
        }
        for (int i = m; i < 10; i++) {//i 从 m 开始
            int t = arr[i];
            arr[i] = arr[m];
            arr[m] = t;
            dfs(m + 1);
            t = arr[i];
            arr[i] = arr[m];
            arr[m] = t;
        }
    }
}

立方变自身

有一个数 N，若它的各位相加等于它本身

8³=512 5+1+2=8

求总共有多少个这样的数

代码：

public static void main(String[] args) {
    int ans = 0;
    for (int i = 1; i < 30; i++) {// 最大到 27，实际运算中将范围扩大
        int pow = (int) Math.pow(i, 3);
        int sum = 0;
        while (pow != 0) {
            sum += pow % 10;
            pow /= 10;
        }
        if (sum == i)
            ans++;
    }
    System.out.println(ans);
}

加法变乘法

题目：
1+2+3+4+···+49=1225
将其中两个不相邻的加号变为乘号，使得结果变为 2015

1+2+3+···+1011+12+···+2728+29+···+49=2015

寻找另一个符合条件的答案，将左边的数进行提交

思路：

1. 两个乘号也就是改变四个数，那可以设置两层循环进行控制
2. 首先定义 sum=1225，让 sum 减去第一层循环的 i 和 i+1，然后减去第二层的 j 和 j+1，得到的值再加上 i*(i+1) 和 j*(j+1)，若最后的结果 ==2015，输出 i 即可

代码：

public static void main(String[] args) {
    for (int i = 1; i <= 49; i++) {
        for (int j = i + 1; j <= 49; j++) {//i 要与后边的数相乘，所以 j 从 i+1 开始
            int ans = 1225;
            ans -= i + (i + 1);
            ans -= j + (j + 1);
            ans += i * (i + 1) + j * (j + 1);
            if (ans == 2015)
                System.out.println(i + " " + j);
        }
    }
}

穿越雷区

题目：
坦克必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从 A 区到 B 区去（A，B 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：

A + - + -

- + - - +

- + + + -

+ - + - +

B + - + -

坦克车只能水平或垂直方向上移动到相邻的区。
数据格式要求：
输入第一行是一个整数 n，表示方阵的大小， 4<=n<100
接下来是 n 行，每行有 n 个数据，可能是 A，B，+，- 中的某一个，中间用空格分开。
A，B 都只出现一次。
要求输出一个整数，表示坦克从 A 区到 B 区的最少移动步数。
如果没有方案，则输出 -1

样例输入

5

A + - + -

- + - - +

- + + + -

+ - + - +

B + - + -

样例输出
10

思路：

1. 最短路径用 BFS 较好，但需要考虑优先队列的使用，这里采用 DFS+ 最大值比较的方式
2. 需要设置的有，标记数组 flag 和前进数组 next
3. dfs 出口可以采用 String 自带的。equals 比较，判断当前数组的内容是否为 "B"，寻找所有的路径进行比较，只保留最小值
4. DFS 体，需要考虑越界和是否正负极连续以及标记数组是否为零

代码：

public class AcrossMinefield {
    static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};// 下一步的方向，分别为：上，下，左，右
    static int ans = Integer.MAX_VALUE;// 取最小，先赋予一个较大值

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[][] map = new String[n][n];// 记录地图
        int[][] flag = new int[n][n];// 1 代表访问过，0 代表未访问过
        int x = 0;
        int y = 0;// 入口坐标
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                map[i][j] = sc.next();// 用空格分割，按字符串存储
                if (map[i][j].equals("A")) {
                    x = i;
                    y = j;
                }
            }
        }
        dfs(map, flag, x, y, 0);
        System.out.println(ans);
        sc.close();
    }

    public static void dfs(String[][] map, int[][] visit, int row, int col, int step) {
        if (map[row][col].equals("B")) {// 到达 B 为出口
            if (step < ans)
                ans = step;
            return;
        }
        visit[row][col] = 1;// 将走过的点标记
        for (int i = 0; i < next.length; i++) {
            int nextRow = row + next[i][0];
            int nextCol = col + next[i][1];// 下一步
            if (nextRow < 0 || nextRow >= map.length || nextCol < 0 || nextCol >= map.length)
                continue;// 越界直接进入下一层循环
            if (visit[nextRow][nextCol] == 0) {// 没有走过
                visit[nextRow][nextCol] = 1;
                if (!map[nextRow][nextCol].equals(map[row][col]))// 不能相等，必须 +- 交替
                    dfs(map, visit, nextRow, nextCol, step + 1);
                visit[nextRow][nextCol] = 0;// Reset in trace
            }
        }
    }
}

表格计算

题目：
某次无聊中， atm 发现了一个很老的程序。这个程序的功能类似于 Excel ，它对一个表格进行操作。
不妨设表格有 n 行，每行有 m 个格子。
每个格子的内容可以是一个正整数，也可以是一个公式。
公式包括三种：

1. SUM(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的和。
2. AVG(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的平均数。
3. STD(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的标准差。

标准差即为方差的平方根。

方差就是：每个数据与平均值的差的平方的平均值，用来衡量单个数据离开平均数的程度。

公式都不会出现嵌套。
如果这个格子内是一个数，则这个格子的值等于这个数，否则这个格子的值等于格子公式求值结果。
输入这个表格后，程序会输出每个格子的值

输入格式
第一行两个数 n, m 。
接下来 n 行输入一个表格。每行 m 个由空格隔开的字符串，分别表示对应格子的内容。
输入保证不会出现循环依赖的情况，即不会出现两个格子 a 和 b 使得 a 的值依赖 b 的值且 b 的值依赖 a 的值。

输出格式
输出一个表格，共 n 行，每行 m 个保留两位小数的实数。
数据保证不会有格子的值超过 1e6 。

样例输入

3 2

1 SUM(2, 1:3, 1)
2 AVG(1, 1:1, 2)
SUM(1, 1:2, 1) STD(1, 1:2, 2)

样例输出

1.00 5.00

2.00 3.00
3.00 1.48

思路：

1. 因为有 SUM(2,1:3,1) 这种形式的输入，所以必须用字符串进行存储，定义一个string[][]
2. 存储完成后进行遍历，对每个数组的第一位进行检查，不是数字则放入方法中进行检查
3. 检查方法，首先要将括号中的坐标进行记录，可以用 int[] 记录对下标为 4、6、8、10 进行 -'0’处理转换为整型
4. 然后截取前三位进行字母比较判断其是哪种方法，然后分情况进行处理

代码：

public class TableCalculation {
    static int n, m;// 表格规模
    static String[][] s = new String[55][55];
    static double[][] val = new double[55][55];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = sc.next();
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i][j].charAt(0) < '0' || s[i][j].charAt(0) > '9') {
                    val[i][j] = convert(s[i][j]);// 如果数组中存放的不是正常数字，就放到转换方法中
                } else {
                    val[i][j] = Double.parseDouble(s[i][j]);// 是的话转换为 double 型
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < m; j++) {
                System.out.printf("%.2f ", val[i][j]);
            }
            System.out.printf("%.2f\n", val[i][m]);
        }
    }

    static int[] sub(String s) {// 找到方法中坐标的值，放入 c[1]~c[4]
        int[] c = new int[6];
        for (int i = 0; i < c.length; i++)
            c[i] = 0;
        c[1] = s.charAt(4) - '0';
        c[2] = s.charAt(6) - '0';
        c[3] = s.charAt(8) - '0';
        c[4] = s.charAt(10) - '0';
        return c;
    }

    static double convert(String string) {// 将公式进行判断转换
        int c[] = sub(string);
        if (string.substring(0, 3).equals("SUM")) {
            return sum(c);
        } else if (string.substring(0, 3).equals("STD")) {
            return std(c);
        } else
            return avg(c);
    }

    static double sum(int a[]) {
        double ans = 0;

        for (int i = a[1]; i <= a[3]; i++) {
            for (int j = a[2]; j <= a[4]; j++) {// 根据坐标范围就所有的集合
                if (s[i][j].charAt(0) < '0' || s[i][j].charAt(0) > '9')
                    ans += convert(s[i][j]);
                else
                    ans += Double.parseDouble(s[i][j]);// 转换为 double 型
            }
        }
        return ans;
    }

    static double avg(int a[]) {
        double ans = sum(a);
        double cnt = (a[3] - a[1] + 1) * (a[4] - a[2] + 1);// 根据方格数求出个数
        return ans / cnt;
    }

    static double std(int a[]) {// 求方差
        double ans = 0;
        double ave = avg(a);
        double cnt = (a[3] - a[1] + 1) * (a[4] - a[2] + 1);
        for (int i = a[1]; i <= a[3]; i++) {
            for (int j = a[2]; j <= a[4]; j++) {
                if (s[i][j].charAt(0) < '0' || s[i][j].charAt(0) > '9')
                    ans += (convert(s[i][j]) - ave) * (convert(s[i][j]) - ave);
                else
                    ans += (Double.parseDouble(s[i][j]) - ave) * (Double.parseDouble(s[i][j]) - ave);

            }
        }
        return Math.sqrt(ans / cnt);
    }
}

2014 年

国王的遗产

题目：
国王 K 有 6 个儿子。在临终前，K 国王立下遗嘱：国王的一批牛作为遗产要分给他的 6 个儿子。
其中，大儿子分 1/4，二儿子 1/5，三儿子 1/6，…
直到小儿子分 1/9。
牛是活的，不能把一头牛切开分。
最后还剩下 11 头牛，分给管家。
请计算国王这批遗产中一共有多少头牛。

思路：

1. 首先牛必须是整只，所以用最后的数取整，但比例必须用双精度存储
2. 用 1 减去每个儿子所占的比例，就是最后 11 头牛剩余的，用11/ 所占比 = 总数

代码：

public static void main(String[] args) {
    double m = 1 - 1 / 4.0 - 1 / 5.0 - 1 / 6.0 - 1 / 7.0 - 1 / 8.0 - 1 / 9.0;//11 头牛所占的比例
    System.out.println(11 / m);//11 除以自身的比例等于全部
}

六角幻方

题目：
把 1 2 3 … 19 共 19 个整数排列成六角形状，如下：
要求每个直线上的数字之和必须相等。共有 15 条直线哦！
预先填好了 2 个数字，第一行的头两个数字是：15 13。
请你填写出中间一行的 5 个数字。数字间用空格分开

思路：

1. 在不改变前两个数字的情况下进行全排列
2. 剪枝，每遍历完一行，就进行横向和斜向的对比

代码：

public class MagicHexagon {
    static int[] a = new int[]{15, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 17, 18, 19};
    static int ans = 0;

    public static void main(String[] args) {
        dfs(2);
        System.out.println(ans);
    }

    static void dfs(int m) {
        if (m == 7) {
            if (a[0] + a[1] + a[2] != a[3] + a[4] + a[5] + a[6])
                return;
        }
        if (m == 12) {
            if (a[0] + a[1] + a[2] != a[7] + a[8] + a[9] + a[10] + a[11])
                return;
            if (a[0] + a[1] + a[2] != a[0] + a[3] + a[7])
                return;
            if (a[0] + a[1] + a[2] != a[2] + a[6] + a[11])
                return;
        }
        if (m == 16) {
            if (a[0] + a[1] + a[2] != a[12] + a[13] + a[14] + a[15])
                return;
            if (a[0] + a[1] + a[2] != a[1] + a[4] + a[8] + a[12])
                return;
            if (a[0] + a[1] + a[2] != a[1] + a[5] + a[10] + a[15])
                return;
        }
        if (m == 19) {
            if (a[0] + a[1] + a[2] != a[16] + a[17] + a[18])
                return;
            if (a[0] + a[1] + a[2] != a[7] + a[12] + a[16])
                return;
            if (a[0] + a[1] + a[2] != a[3] + a[8] + a[13] + a[17])
                return;
            if (a[0] + a[1] + a[2] != a[0] + a[4] + a[9] + a[14] + a[18])
                return;

            if (a[0] + a[1] + a[2] != a[11] + a[15] + a[18])
                return;
            if (a[0] + a[1] + a[2] != a[6] + a[10] + a[14] + a[17])
                return;
            if (a[0] + a[1] + a[2] != a[2] + a[5] + a[9] + a[13] + a[16])
                return;
        }

        if (m >= 19) {
            for (int i = 7; i <= 11; i++)
                System.out.print(a[i] + " ");
            System.out.println();
            ans++;
            return;
        }

        for (int i = m; i < 19; i++) {
            int t = a[i];
            a[i] = a[m];
            a[m] = t;
            dfs(m + 1);
            t = a[i];
            a[i] = a[m];
            a[m] = t;
        }
    }
}

排列序数

题目：
如果用 a b c d 这 4 个字母组成一个串，有 4!=24 种，如果把它们排个序，每个串都对应一个序号：

abcd 0

abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17

现在有不多于 10 个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？
【输入格式】
一行，一个串。
【输出格式】
一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 0。
输入：
bdca
程序应该输出：
11
输入：
cedab
程序应该输出：
70

思路：

1. 先用递归进行模拟，从 ACSII 码 97（全小写字母）开始遍历，记录 97+length 的 n 个字符，然后与输入的字符串进行比对
2. 先模拟再放入递归中，以便于反向调换不至于影响顺序

代码：

public class ArrangeNumber {
    static int len = 0;
    static char[] res = new char[10];
    static int[] mark = new int[150];
    static long count = -1;// 序号从零开始，所以计数初始值为 -1

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        len = str.length();// 记录字符串的长度
        dfs(0, str);
        sc.close();
    }

    public static void dfs(int n, String end) {
        if (len == n) {
            count++;// 序号 +1
            String str = String.valueOf(res).trim();// 将字符数组转换为字符串，没有 trim 会错误
            if (str.equals(end)) {// 等于输入的值说明模拟成功
                System.out.println(count);
            }
            return;
        }

        for (int i = 97; i < 97 + len; i++) {// 字母全小写，从 ASCII 值 97 开始
            if (mark[i] == 0) {// 标记是否使用，防止一串字符中出现相同的字母
                res[n] = ((char) i);
                mark[i] = 1;
                dfs(n + 1, end);// 先模拟后递归，到达出口后反向调换
                mark[i] = 0;
            }
        }
    }
}

2013 年

猜灯谜

题目：
有一个灯谜公式：

请猜谜 * 请猜谜 = 请边赏灯边猜

若是用数字代替汉字，那么符合公式条件的“请猜谜”的三位数字是哪一个

思路：

1. 读入数字可以采用每位分开多层循环嵌套，方便后续的计算
2. 枚举法对范围的判定：请猜谜的平方是一个六位数，所以从 317 开始至 999
3. 取余法将六位数的所需判断位保存下来（取 X 位，就用 N%(X+1)/X）
4. 在输出语句前加上双引号，使得整型直接按字符串输出System.out.println("" + a + b + c);

代码：

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    for (int a = 3; a <= 9; a++) {// 从 317 开始结果才可能为六位
        for (int b = 0; b <= 9; b++) {
            if (a != b) {//" 请 " 和 " 猜 " 必须不相同
                for (int c = 0; c <= 9; c++) {
                    int num = a * 100 + b * 10 + c;
                    int pownum = num * num;
                    int shiwan = pownum / 100000;
                    int wan = pownum % 100000 / 10000;
                    int shi = pownum % 100 / 10;
                    int ge = pownum % 10;// 取 X 位，就用 N%(X+1)/X
                    if (a == shiwan && b == ge && wan == shi)
                        System.out.println("" + a + b + c);// 通过加 "" 使 int 型输出为 String
                }
            }
        }
    }
}

连续奇数的和

题目：
任何数的立方都可以表示为连续奇数的和

2³=8=3+5

3³=27=7+9+11
4³=64=1+3+···+15

那么 111³的连续奇数和表示法的第一个数字为？

思路：

1. 设立双循环嵌套，每个循环的变量为i+=2，这样确保每次的都是奇数，定义 sum 将第二层循环的变量全部相加，当与 pow(111,3) 相等时，便输出第一层循环的变量值
2. 采用等差数列的思维，奇数的求和公式为Sn=n*n，当全部的数列和减去前 N 项数列和的值与 pow(111,3) 相等时，就可以确定 N 为第几项，然后用奇数等差数列的求项公式An=2*n-1, 将起始项（第 N 项）的值求出
3. 循环中进行判断当输出之后就可结束程序：System.exit(0);

代码：

public static void main(String[] args) {
    int n = (int) Math.pow(111, 3);
    // 方法一：枚举所有奇数项
    for (int i = 1; i <= n; i += 2) {//i 每次加 2 确保为奇数
        int sum = 0;
        for (int j = i; j <= n; j += 2) {// 让 j 的初始值等于 i
            sum += j;// 只要 sum<=n 便一直加后边的奇数
            if (sum > n)
                break;
            if (sum == n) {
                System.out.println(i);
                System.exit(0);// 直接退出
            }
        }
    }
        // 方法二：利用奇数等差数列
    // 奇数等差数列的求和公式：Sn=n*n; 求项：An=2*n-1;
    // 将所有的奇数排列在一起：1，3，5，7···，end
    // 从第 n 位开始一直到 end 的和 ==pow(111,3)，也就是 sum(1-end)-sum(1-(n-1))==pow(111,3)
    // 由此可以确定第 n 项的值，根据 An=2*n-1 得出具体的数字
    for (int i = 1; i < 3000; i++) {
        for (int j = i; j < 3000; j++) {
            if (j * j - (i - 1) * (i - 1) == n) {
                System.out.println(2 * i - 1);
                System.exit(0);
            }
        }
    }
}

迷宫

题目：
定义一个 x*y 的地图，其中 0 表示通路，1 表示死路
代码：

/**
    * DFS 算法解决走迷宫问题
    * 0: 表示通路
    * 1: 表示死路
    */
static String path = "";
static String shortestPath = "";

public static void main(String[] args) {
    // 初始化一个迷宫地图
    // 0: 表示通路
    // 1: 表示死路
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int y = sc.nextInt();
    int count = 0;
    int[][] map = new int[x][y];
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++)
            map[i][j] = sc.nextInt();

    /*
        * 从矩阵的左上角位置开始搜索
        * */
    dfs(0, 0, map);
    if (shortestPath.length() != 0)
        System.out.println(" 最短路线为：" + shortestPath);
    else
        System.out.println(" 没有找到路线！");
    char[] s = shortestPath.toCharArray();
    for (char c : s) {
        if (c == '-')
            count++;
    }
    System.out.println(count);
}

public static void dfs(int x, int y, int[][] map) {
    /*
        * 获得矩阵的大小
        * */
    int m = map.length;
    int n = map[0].length;
    // 设置结束条件
    if (x < 0 || y < 0)
        return;
    // 如果坐标越界，或者 maze[x][y]==1 表示遇到障碍
    if (x > m - 1 || y > n - 1)
        return;
    // 表示遇到障碍
    if (map[x][y] == 1)
        return; // 判断是否通路和越界
    if (x == m - 1 && y == n - 1) { // 判断是否抵达出口
        path = path + "(" + x + "," + y + ")";
        if (shortestPath.length() == 0 || shortestPath.length() > path.length())
            shortestPath = path;
        System.out.println(" 找到路线：" + path);
        return;
    }

    String temp = path;
    path = path + "(" + x + "," + y + ")" + "-"; // 记录路线
    map[x][y] = 1; // 将走过的路标记
    // 向四个方向搜索
    dfs(x + 1, y, map);  // 向右搜索
    dfs(x, y + 1, map);  // 向下搜索
    dfs(x, y - 1, map);  // 向上搜索
    dfs(x - 1, y, map);  // 向左搜索
    // 将路线和标记恢复成上一次的状态
    map[x][y] = 0;
    // 清除
    path = temp;
}

背包

0-1 背包

题目：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 U_i，价值是 W_i。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N， V，用空格隔开，分别表示物品数量和背包容积。
接下来 N 行，每行两个整数 u, w; ，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
输入样例

4 5

1 2
2 4
3 4
4 5

输出样例

8

代码：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        int[] v=new int[N];
        int[] w=new int[N];
        for(int i=0;i<N;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
        }
        // int[][] dp=new int[N+1][V+1];
        // for(int i=1;i<=N;i++){
        //     for(int j=0;j<=V;j++){
        //         dp[i][j]=dp[i-1][j];
        //         if(j-v[i-1]>=0){
        //             dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);
        //         }
        //     }
        // }
        //  System.out.println(dp[N][V]);
        int[] dp=new int[V+1];
        for(int i=1;i<=N;i++){
            // 从大到小遍历
            for(int j=V;j>=0;j--){
                if(j>=v[i-1]){
                    dp[j]=Math.max(dp[j],dp[j-v[i-1]]+w[i-1]);
                }
            }
        }
        System.out.println(dp[V]);
    }
}

完全背包

题目：
有 N 件物品和一个容量是 V 的背包。每件物品有无数件。
第 i 件物品的体积是 U_i，价值是 W_i。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N， V，用空格隔开，分别表示物品数量和背包容积。
接下来 N 行，每行两个整数 u, w; ，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
输入样例

4 5

1 2
2 4
3 4
4 5

输出样例

10

代码：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        int[] v=new int[N];
        int[] w=new int[N];
        for(int i=0;i<N;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
        }
        int[] dp=new int[V+1];
        for(int i=0;i<N;i++){
            // 代码与 01 背包的区别，从小到大遍历
            for(int j=0;j<=V;j++){
                if(j>=v[i]){
                    dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[V]);
    }
}

多重背包（普通）

每件物品有了个数，输入时输入三个值：体积、价值、数量

代码：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        int[] v=new int[N];
        int[] w=new int[N];
        int[] s=new int[N];
        for(int i=0;i<N;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
            s[i]=sc.nextInt();
        }
        // int[][] dp=new int[N+1][V+1];
        // for(int i=1;i<=N;i++){
        //     for(int j=0;j<=V;j++){
        //         for(int k=0;k<=s[i-1];k++){
        //             if(j>=k*v[i-1]){
        //                 dp[i][j]=Math.max(dp[i][j],dp[i-1][j-k*v[i-1]]+k*w[i-1]);
        //             }
        //         }
        //     }
        // }
        // System.out.println(dp[N][V]);
        int[] dp=new int[V+1];
        for(int i=1;i<=N;i++){
            // 01 背包扩展，体积从大到小遍历
            for(int j=V;j>=0;j--){
                // 对物品数量进行遍历
                for(int k=0;k<=s[i-1];k++){
                    if(j>=k*v[i-1]){
                        dp[j]=Math.max(dp[j],dp[j-k*v[i-1]]+k*w[i-1]);
                    }
                }
            }
        }
        System.out.println(dp[V]);
    }
}

多重背包（大型数据）

代码：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        int[] v=new int[N];
        int[] w=new int[N];
        int[] s=new int[N];
        for(int i=0;i<N;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
            s[i]=sc.nextInt();
        }
        List<good> goods=new ArrayList<>();
        // 转化为 01 背包问题，把物品数量拆成二进制组合，组合数能取到 0~s 中任意一个数
        for(int i=0;i<N;i++){
            for(int k=1;k<=s[i];k=k*2){
                s[i]=s[i]-k;
                goods.add(new good(k*v[i],k*w[i]));
            }
            if(s[i]>0){
                goods.add(new good(s[i]*v[i],s[i]*w[i]));
            }
        }
        int[] dp=new int[V+1];
        for(int i=1;i<=goods.size();i++){
            for(int j=V;j>=0;j--){
                if(j>=goods.get(i-1).v){
                    dp[j]=Math.max(dp[j],dp[j-goods.get(i-1).v]+goods.get(i-1).w);
                }
            }
        }
        System.out.println(dp[V]);
    }
}
class good{
    int v;
    int w;
    public good(int v,int w){
        this.v=v;
        this.w=w;
    }
}

混合背包

题目：
有 N 件物品和一个容量是 V 的背包。
物品一共有三类

1. 第一类物品只能用一次
2. 第二类物品可以用无限次
3. 第三类物品可以用 i 次

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N， V，用空格隔开，分别表示物品数量和背包容积。
接下来 N 行，每行两个整数 u, w, s; ，用空格隔开，分别表示第 i 件物品的体积、价值和数量。

• s==-1, 表示物品只能用一次
• s==0, 表示物品可以用无限次
• s>0, 表示物品可以使用 s 次

输出格式
输出一个整数，表示最大价值。
输入样例

4 5

1 2 -1
2 4 1
3 4 0
4 5 2

输出样例

8

代码：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        List<Thing> things=new ArrayList<>();
        for(int i=0;i<N;i++){
            int v=sc.nextInt();
            int w=sc.nextInt();
            int s=sc.nextInt();
            if(s<0){
                things.add(new Thing(-1,v,w));
            }else if(s==0){
                things.add(new Thing(0,v,w));
            // 多重背包转化为 01 背包
            }else{
                for(int k=1;k<=s;k=k*2){
                    s=s-k;
                    things.add(new Thing(-1,k*v,k*w));
                }
                if(s>0){
                    things.add(new Thing(-1,s*v,s*w));
                }
            }
        }
        int[] dp=new int[V+1];
        for(int i=1;i<=things.size();i++){
            int kind=things.get(i-1).kind;
            if(kind<0){
                // 01 背包，体积从大到小遍历
                for(int j=V;j>=things.get(i-1).v;j--){
                    dp[j]=Math.max(dp[j],dp[j-things.get(i-1).v]+things.get(i-1).w);
                }
            }else{
                // 完全背包，体积从小到大遍历
                for(int j=things.get(i-1).v;j<=V;j++){
                    dp[j]=Math.max(dp[j],dp[j-things.get(i-1).v]+things.get(i-1).w);
                }
            }
        }
        System.out.println(dp[V]);
    }
}
class Thing{
    int kind;
    int v;
    int w;
    public Thing(int kind,int v,int w){
        this.kind=kind;
        this.v=v;
        this.w=w;
    }
}