46. 携带研究材料（第六期模拟笔试）

时间限制：5.000S空间限制：128MB

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例

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

输出示例

5

提示信息

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。

数据范围：
$1\le N\le 5000$
$1\le M\le 5000$
研究材料占用空间和价值都小于等于 1000

解法一(动态规划)

思路分析：

1. 背包问题，使用动态规划算法；由动规五步曲得：
2. 确定dp数组及下标含义；二维数组 dp[i][j] 表示前 i 个物品中，背包容量为 j 时的最大价值。
3. 确定动态转移方程；当确定某个物品i是否加入背包时有以下两种情况：
   1. 该物件加入背包：dp[i][j] = dp[i - 1][j - spaces[i]] + values[i]；因为该物品加入背包，则需要减去该物品的空间，并加上该物品的价值。即减去该物品所占空间；剩下空间的最大价值加该物品的价值
   2. 该物品不加入背包：dp[i][j] = dp[i - 1][j]
   3. 因此状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - spaces[i]] + values[i])
4. 确定dp数组的初始化；因为空间为 0 时，无法放入物品，所以最大价值为 0；所以初始化时，dp[i][0] = 0；同时当只有一个物品时，dp[0][j] = values[0]，因为只有 1 个物品，所以只有一种情况，即该物品加入背包，所以最大价值为该物品的价值。同时也要注意物品无法加入背包时，最大价值只能为0
5. 确定遍历顺序；从左上角开始遍历，因为需要知道 dp[i - 1][j] 的值，所以需要先遍历物品，再遍历背包。
6. 将dp数组打印，检验是否符合思路和题意

实现代码如下：

import java.util.Arrays;
import java.util.Scanner;

/**
 * 46. 携带研究材料（第六期模拟笔试）
 * @author 花木凋零成兰
 * @date 2024/4/6 11:24
 */
public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int m = in.nextInt();   // 研究材料种类
        int n = in.nextInt();   // 行李空间

        int[] a = new int[m];   // 每种研究材料所占空间
        for (int i = 0; i < m; i++) {
            a[i] = in.nextInt();
        }
        int[] b = new int[m];   // 每种研究材料的价值
        for (int i = 0; i < m; i++) {
            b[i] = in.nextInt();
        }

        // 检验输入是否有问题
//        System.out.println(m);
//        System.out.println(n);
//        System.out.println(Arrays.toString(a));
//        System.out.println(Arrays.toString(b));

        // 输出结果
        System.out.println(BringResearchMaterials(m, n, a, b));

    }

    private static int BringResearchMaterials(int m, int n, int[] spaces, int[] values) {

        // 1. dp数组的含义：dp[i][j] 表示任取[0,j]的物品 放入容量为j的背包中 的最大价值
        int[][] dp = new int[m+1][n+1];
        // 2. dp数组的递推公式
        // 不放物品i时 dp[i][j] = dp[i-1][j]
        // 放物品i时 dp[i][j] = dp[i-1][j-values[i]] + values[i]
        // 所以递推公式为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-values[i]] + values[i])
        // 3. dp数组的初始化
        // 背包容量为0时 即j=0 此时背包无法放入研究材料 dp[i][0]均为0
        // 对于只有物品0时 判断其是否为可以放入背包 可以则放入dp[0][j]=values[i] 不可以则dp[0][j]=0
        for (int j = 1; j <= n; ++ j) {
            if (j >= spaces[0]) {
                dp[0][j] = values[0];
            }
        }
        // 4. dp数组的遍历顺序
        // 根据dp数组定义 第一层循环遍历物品 从左往右
        // 第二层循环则 背包容量 从小到大
        for (int i = 1; i < m; ++ i) {
            for (int j = 1; j <= n; ++j) {
                if (j >= spaces[i]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-spaces[i]] + values[i]);
                } else dp[i][j] = dp[i-1][j];
            }
        }

        // 5. 打印dp数组
        // System.out.println(Arrays.deepToString(dp));
        return dp[m-1][n];
    }

}

提交结果如下：

time_space_table: /1046/sample.in:AC mem=12728k time=161ms /1046/test1.in:AC mem=12824k time=166ms /1046/test10.in:AC mem=42760k time=426ms /1046/test2.in:AC mem=42760k time=160ms /1046/test3.in:AC mem=42760k time=168ms /1046/test4.in:AC mem=42760k time=182ms /1046/test5.in:AC mem=42760k time=235ms /1046/test6.in:AC mem=42760k time=268ms /1046/test7.in:AC mem=42760k time=304ms

复杂度分析：

• 时间复杂度：$O(N\ast M)$，其中 N 为物品数量，M 为背包容量
• 空间复杂度：$O(N\ast M)$，其中 N 为物品数量，M 为背包容量

解法二(滚动数组)

思路分析：

1. 由解法一的状态转移方程可以发现，只需要保存上一行和当前行的状态即可，因此可以使用滚动数组优化空间复杂度。
2. 即状态转移方程可以优化为dp[j] = max(dp[j], dp[j - spaces[i]] + values[i])；且dp[j]表示背包容量为j时的最大价值。
3. 即对dp数组的初始化为：因为j=0时，背包内无法放入研究材料，所以dp[0] = 0
4. 确定遍历顺序，先遍历物品，再遍历背包。同时遍历背包时，应该从右开始遍历，因为确定当前行的状态需要先知道上一行dp[j - spaces[i]]的值。若从左开始遍历，则此时的dp[j - spaces[i]]的值为当前行的状态，已经被更新了。
5. 将dp数组打印，检验是否符合思路和题意

实现代码如下：

import java.util.Arrays;
import java.util.Scanner;

/**
 * 46. 携带研究材料（第六期模拟笔试）
 * @author 花木凋零成兰
 * @date 2024/4/6 11:24
 */
public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int m = in.nextInt();   // 研究材料种类
        int n = in.nextInt();   // 行李空间

        int[] a = new int[m];   // 每种研究材料所占空间
        for (int i = 0; i < m; i++) {
            a[i] = in.nextInt();
        }
        int[] b = new int[m];   // 每种研究材料的价值
        for (int i = 0; i < m; i++) {
            b[i] = in.nextInt();
        }

        // 检验输入是否有问题
//        System.out.println(m);
//        System.out.println(n);
//        System.out.println(Arrays.toString(a));
//        System.out.println(Arrays.toString(b));

        // 输出结果
        System.out.println(BringResearchMaterials(m, n, a, b));

    }

    /**
     * 动态规划 —— 滚动数组
     * @param m 材料种类数
     * @param n 空间大小
     * @param spaces    每种材料所占空间
     * @param values    每种材料所占价值
     * @return
     */
    private static int BringResearchMaterials(int m, int n, int[] spaces, int[] values) {

        // 1. dp数组的含义：dp[j] 表示任取[0,i]的物品 放入容量为j的背包中 的最大价值
        int[] dp = new int[n+1];
        // 2. dp数组的递推公式
        // 不放物品i时 dp[j] = dp[j]
        // 放物品i时 dp[j] = dp[j-values[i]] + values[i]
        // 所以递推公式为： dp[j] = max(dp[j], dp[j-values[i]] + values[i])
        // 3. dp数组的初始化
        // 背包容量为0时 即j=0 此时背包无法放入研究材料 dp[0]为0
        dp[0] = 0;
        // 4. dp数组的遍历顺序
        // 根据dp数组定义 第一层循环遍历物品 从左往右
        // 第二层循环则 背包容量 从大到小
        for (int i = 0; i < m; ++ i) {
            for (int j = n; j >= 1; --j) {
                if (j >= spaces[i]) {
                    dp[j] = Math.max(dp[j], dp[j - spaces[i]] + values[i]);
                }
            }
        }

        // 5. 打印dp数组
        // System.out.println(Arrays.deepToString(dp));
        return dp[n];
    }
}

提交结果如下：

time_space_table: /1046/sample.in:AC mem=12880k time=163ms /1046/test1.in:AC mem=12880k time=158ms /1046/test10.in:AC mem=18320k time=372ms /1046/test2.in:AC mem=18320k time=157ms /1046/test3.in:AC mem=18320k time=161ms /1046/test4.in:AC mem=18320k time=185ms /1046/test5.in:AC mem=18320k time=247ms /1046/test6.in:AC mem=18320k time=242ms /1046/test7.in:AC mem=18320k time=294ms

复杂度分析：

• 时间复杂度：$O(N\ast M)$，其中 N 为物品数量，M 为背包容量
• 空间复杂度：$O(N)$，其中 N 为背包容量