马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
46. 携带研究材料（第六期模拟笔试）
题目形貌
小明是一位科学家，他需要到场一场告急的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验装备、文献资料和实验样本等等，它们各自占据差别的空间，而且具有差别的价值。小明的行李空间为 N，问小明应该如何决议，才气携带最大价值的研究材料。每种研究材料只能选择一次，而且只有选与不选两种选择，不能进行切割。
解题思绪
这是一个典型的01背包问题，我们可以使用动态规划来解决这个问题。
- 定义状态：dp[j] 表示在前 i 件物品中选择，使得总体积不凌驾 j 的情况下，这些物品的最大价值。
- 状态初始化：
- dp[0][..] 表示只考虑第一件物品时，差别容量下的最大价值。
- dp[..][0] 表示背包涵量为0时，无论多少件物品，价值都是0。
- 状态转移方程：
- 假如当前物品的重量大于背包的剩余容量，则不能选择该物品，即 dp[j] = dp[i-1][j]。
- 假如可以选择该物品，则需要决议是选择该物品还是不选择，即 dp[j] = max(dp[i-1][j], dp[i-1][j-weight] + value)。
- 终极答案：dp[n-1][bagweight] 即为最大价值。
代码实现
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- int bagweight = scanner.nextInt();
- int[] weight = new int[n];
- int[] value = new int[n];
- for (int i = 0; i < n; ++i) {
- weight[i] = scanner.nextInt();
- }
- for (int j = 0; j < n; ++j) {
- value[j] = scanner.nextInt();
- }
- int[][] dp = new int[n][bagweight + 1];
- for (int i = weight[0]; i <= bagweight; i++) {
- dp[0][i] = value[0];
- }
- for (int i = 1; i < n; i++) {
- for (int j = 0; j <= bagweight; j++) {
- if (j < weight[i]) {
- dp[i][j] = dp[i - 1][j];
- } else {
- dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- }
- }
- }
- System.out.println(dp[n - 1][bagweight]);
- }
- }
解法二是使用一维数组来优化01背包问题的动态规划解法。以下是详细的解题步调：
- 定义状态：使用一维数组 dp[j] 表示背包涵量为 j 时的最大价值。
- 状态初始化：初始化 dp[0] 为 0，因为背包涵量为0时，价值为0。
- 状态转移方程：对于每个物品，从背包涵量大到小进行遍历，更新 dp[j] 的值。假如当前物品的重量小于等于背包的剩余容量 j，则更新 dp[j] 为 max(dp[j], dp[j - weight] + value)。
- 由于每个物品只能选择一次，以是需要从大到小遍历背包涵量，以防止一个物品被重复计算。
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- int bagweight = scanner.nextInt();
- int[] weight = new int[n];
- int[] value = new int[n];
- for (int i = 0; i < n; ++i) {
- weight[i] = scanner.nextInt();
- }
- for (int j = 0; j < n; ++j) {
- value[j] = scanner.nextInt();
- }
- int[] dp = new int[bagweight + 1];
- for (int i = 1; i < n; i++) {
- for (int j = bagweight; j >= weight[i]; j--) {
- dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
- }
- }
- System.out.println(dp[bagweight]);
- scanner.close();
- }
- }
题目形貌
给定一个只包罗正整数的非空数组，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意：数组中的每个元素不会凌驾 100，数组的大小不会凌驾 200。
力扣题目链接：分割等和子集
解题思绪
这个问题可以转化为一个背包问题，即判断是否存在一种方式，使得从数组中选取的若干元素之和等于所有元素总和的一半。
- 计算目标和：首先计算数组所有元素的总和，假如总和为奇数，则不可能分割成两个和相等的子集，直接返回 false。
- 初始化动态规划数组：假如总和为偶数，则目标和为总和的一半。创建一个动态规划数组 dp，其中 dp[j] 表示背包涵量为 j 时，能够装入的最大价值。
- 动态规划填表：遍历每个元素，并更新动态规划数组。对于每个元素 nums，从目标值 target 开始向下遍历到 nums，更新 dp[j] 为 max(dp[j], dp[j-nums] + nums)。
- 判断结果：假如 dp[target] 等于 target，则说明存在一种分割方式，使得两个子集的和相等，返回 true；否则返回 false。
以下是实现该解法的代码：
- class Solution {
- public boolean canPartition(int[] nums) {
- int target = 0;
- for(int i=0;i<nums.length;i++){
- target = target + nums[i];
- }
- if(target % 2 != 0) return false;
- target = target/2;
- int[] dp = new int[target+1];
- for(int i =0;i< nums.length;i++){
- for(int j=target;j>=nums[i];j--){
- dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
- }
- }
- if(dp[target] == target){
- return true;
- }else {
- return false;
- }
- }
- }
|
