携带研究材料 | KamaCoder-46 | 动态规划 | 0-1背包问题

发表于 更新于 分类于 ， ， 阅读次数： 阅读次数： Waline： 本文字数： 5.7k 阅读时长 ≈ 9 分钟
动态规划练习题
LeetCode链接：46. 携带研究材料

1.01背包

1.1 题目描述

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

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

输入描述

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

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

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

输出描述

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

输入示例
1
2
3
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
1
5
提示信息

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

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

1.2 题解

1.2.1 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象来读取输入数据
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt(); // 材料的种类数
        int n = sc.nextInt(); // 行李的空间大小

        // 初始化数组来存储材料的重量和价值
        int[] weights = new int[m];
        int[] values = new int[m];

        // 读取每种材料的重量
        for (int i = 0; i < m; i++) {
            weights[i] = sc.nextInt();
        }

        // 读取每种材料的价值
        for (int i = 0; i < m; i++) {
            values[i] = sc.nextInt();
        }

        // 初始化动态规划数组，dp[i][j] 表示前 i 个物品在容量为 j 的背包中可达到的最大价值
        int[][] dp = new int[m][n + 1];

        // 处理第一个物品的情况
        for (int i = weights[0]; i <= n; i++) {
        	dp[0][i] = values[0];
        }

        // 逐件处理物品，更新 dp 数组
        for (int i = 1; i < m; i++) { // 遍历物品
            for (int j = weights[i]; j <= n; j++) { // 遍历背包容量
                // 更新 dp[i][j]，取放入当前物品和不放入当前物品中的最大值
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }

        // 输出背包容量为 n 时的最大价值
        System.out.println(dp[m - 1][n]);
    }
}

1.2.2 动态规划-滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象来读取输入数据
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt(); // 材料的种类数
        int n = sc.nextInt(); // 行李的空间大小

        // 初始化数组来存储材料的重量和价值
        int[] weights = new int[m];
        int[] values = new int[m];

        // 读取每种材料的重量
        for (int i = 0; i < m; i++) {
            weights[i] = sc.nextInt();
        }

        // 读取每种材料的价值
        for (int i = 0; i < m; i++) {
            values[i] = sc.nextInt();
        }

        // 初始化动态规划数组，dp[j] 表示容量为 j 的背包可以装下的物品的最大价值
        int[] dp = new int[n + 1];

        // 逐件处理物品，更新 dp 数组
        // 先处理第一件物品的情况
        for (int i = weights[0]; i <= n; i++) {
            dp[i] = values[0];
        }

        // 逐件处理剩下的物品
        for (int i = 1; i < m; i++) { // 遍历物品
            for (int j = n; j >= weights[i]; j--) { // 从大到小遍历背包容量
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        // 输出背包容量为 n 时的最大价值
        System.out.println(dp[n]);
    }
}

1.2.3 动态规划-滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象来读取输入数据
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt(); // 材料的种类数
        int n = sc.nextInt(); // 行李的空间大小

        // 初始化数组来存储材料的重量和价值
        int[] weights = new int[m];
        int[] values = new int[m];

        // 读取每种材料的重量
        for (int i = 0; i < m; i++) {
            weights[i] = sc.nextInt();
        }

        // 读取每种材料的价值
        for (int i = 0; i < m; i++) {
            values[i] = sc.nextInt();
        }

        // 初始化动态规划数组，dp[j] 表示容量为 j 的背包可以装下的物品的最大价值
        int[] dp = new int[n + 1];

        // 逐件处理剩下的物品
        for (int i = 0; i < m; i++) { // 遍历物品
            for (int j = n; j >= weights[i]; j--) { // 从大到小遍历背包容量
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        // 输出背包容量为 n 时的最大价值
        System.out.println(dp[n]);

        // 关闭 scanner 对象，释放资源
        sc.close();
    }
}

2.完全背包

2.1 题目描述

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

小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

输入描述

第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间

接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值

输出描述

输出一个整数，表示最大价值。

输入示例
1
2
3
4
5
4 5
1 2
2 4
3 4
4 5
输出示例
1
10
提示信息

第一种材料选择五次，可以达到最大值。

数据范围：

1 <= N <= 10000;
1 <= V <= 10000;
1 <= wi, vi <= 10^9.

2.2 题解

2.2.1 滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner; // 导入Scanner类，用于读取控制台输入

public class Main { // 主类定义
    public static void main(String[] args) { // 主函数入口
        Scanner sc = new Scanner(System.in); // 创建Scanner对象用于获取输入
        
        // 读取物品的数量n和背包的最大承重v
        int n = sc.nextInt();
        int v = sc.nextInt();

        // 初始化两个数组，分别存储每个物品的重量和价值
        int[] weights = new int[n];
        int[] values = new int[n];

        // 读取每个物品的重量和价值
        for (int i = 0; i < n; i++) {
            weights[i] = sc.nextInt(); // 读取第i个物品的重量
            values[i] = sc.nextInt(); // 读取第i个物品的价值
        }

        // 初始化一个一维数组dp，长度为背包承重v加一，用于存储动态规划的状态
        int[] dp = new int[v + 1];

        // 动态规划求解最大价值
        for (int i = 0; i < n; i++) { // 遍历每个物品
            for (int j = v; j >= weights[i]; j--) { // 对于每个物品，从背包承重最大的位置开始，逆向遍历到物品重量的位置
                // 更新dp数组中的最大价值
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        // 输出背包的最大价值
        System.out.println(dp[v]);
    }
}

3.多重背包

3.1 题目描述

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入描述

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。

接下来的三行，每行包含 N 个正整数。具体如下：

第二行包含 N 个整数，表示 N 种矿石的重量。

第三行包含 N 个整数，表示 N 种矿石的价格。

第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

输出描述

输出一个整数，代表获取的最大价值。

输入示例
1
2
3
4
10 3
1 3 4
15 20 30
2 3 2
输出示例
1
90
提示信息

数据范围：
1 <= C <= 10000;
1 <= N <= 10000;
1 <= w[i], v[i], k[i] <= 10000;

3.2 题解

3.2.1 转化成01背包-滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.Scanner; // 导入Scanner类，用于读取控制台输入

public class Main { // 主类定义
    public static void main(String[] args) { // 主函数入口
        Scanner sc = new Scanner(System.in); // 创建Scanner对象用于获取输入
        
        // 读取背包的最大容量c和物品的数量n
        int c = sc.nextInt();
        int n = sc.nextInt();

        // 初始化三个数组，分别存储每个物品的重量、价值和数量上限
        int[] w = new int[n];
        int[] v = new int[n];
        int[] k = new int[n];

        // 读取每个物品的重量
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }

        // 读取每个物品的价值
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
        }

        // 读取每个物品的数量上限
        for (int i = 0; i < n; i++) {
            k[i] = sc.nextInt();
        }

        // 初始化一个一维数组dp，长度为背包容量c加一，用于存储动态规划的状态
        int[] dp = new int[c + 1];

        // 动态规划求解最大价值
        for (int i = 0; i < n; i++) { // 遍历每个物品
            for (int j = c; j >= w[i]; j--) { // 对于每个物品，从背包容量最大的位置开始，逆向遍历到物品重量的位置
                // 添加一个内层循环来处理数量上限
                for (int m = 1; m <= k[i] && (j - m * w[i]) >= 0; m++) { // 对于每个物品，尝试不同的数量m
                    // 更新dp数组中的最大价值
                    dp[j] = Math.max(dp[j], dp[j - m * w[i]] + m * v[i]);
                }
            }
        }

        // 输出背包的最大价值
        System.out.println(dp[c]);
    }
}
-------------本文结束感谢您的阅读-------------