代码随想录第三十五天| 46. 携带研究材料（第六期模拟笔试） 416. 分割等和
46. 携带研究材料（第六期模拟笔试）题目形貌
小明是一位科学家，他需要到场一场告急的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验装备、文献资料和实验样本等等，它们各自占据差别的空间，而且具有差别的价值。小明的行李空间为 N，问小明应该如何决议，才气携带最大价值的研究材料。每种研究材料只能选择一次，而且只有选与不选两种选择，不能进行切割。
解题思绪
这是一个典型的01背包问题，我们可以使用动态规划来解决这个问题。
[*]定义状态：dp 表示在前 i 件物品中选择，使得总体积不凌驾 j 的情况下，这些物品的最大价值。
[*]状态初始化：
[*]dp[..] 表示只考虑第一件物品时，差别容量下的最大价值。
[*]dp[..] 表示背包涵量为0时，无论多少件物品，价值都是0。
[*]状态转移方程：
[*]假如当前物品的重量大于背包的剩余容量，则不能选择该物品，即 dp = dp。
[*]假如可以选择该物品，则需要决议是选择该物品还是不选择，即 dp = max(dp, dp] + value)。
[*]终极答案：dp 即为最大价值。
代码实现
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;
int[] value = new int;
for (int i = 0; i < n; ++i) {
weight = scanner.nextInt();
}
for (int j = 0; j < n; ++j) {
value = scanner.nextInt();
}
int[][] dp = new int;
for (int i = weight; i <= bagweight; i++) {
dp = value;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= bagweight; j++) {
if (j < weight) {
dp = dp;
} else {
dp = Math.max(dp, dp] + value);
}
}
}
System.out.println(dp);
}
}
解题思绪
解法二是使用一维数组来优化01背包问题的动态规划解法。以下是详细的解题步调：
[*]定义状态：使用一维数组 dp 表示背包涵量为 j 时的最大价值。
[*]状态初始化：初始化 dp 为 0，因为背包涵量为0时，价值为0。
[*]状态转移方程：对于每个物品，从背包涵量大到小进行遍历，更新 dp 的值。假如当前物品的重量小于等于背包的剩余容量 j，则更新 dp 为 max(dp, dp] + 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;
int[] value = new int;
for (int i = 0; i < n; ++i) {
weight = scanner.nextInt();
}
for (int j = 0; j < n; ++j) {
value = scanner.nextInt();
}
int[] dp = new int;
for (int i = 1; i < n; i++) {
for (int j = bagweight; j >= weight; j--) {
dp = Math.max(dp, dp] + value);
}
}
System.out.println(dp);
scanner.close();
}
}
416. 分割等和子集
题目形貌
给定一个只包罗正整数的非空数组，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意：数组中的每个元素不会凌驾 100，数组的大小不会凌驾 200。
力扣题目链接：分割等和子集
解题思绪
这个问题可以转化为一个背包问题，即判断是否存在一种方式，使得从数组中选取的若干元素之和等于所有元素总和的一半。
[*]计算目标和：首先计算数组所有元素的总和，假如总和为奇数，则不可能分割成两个和相等的子集，直接返回 false。
[*]初始化动态规划数组：假如总和为偶数，则目标和为总和的一半。创建一个动态规划数组 dp，其中 dp 表示背包涵量为 j 时，能够装入的最大价值。
[*]动态规划填表：遍历每个元素，并更新动态规划数组。对于每个元素 nums，从目标值 target 开始向下遍历到 nums，更新 dp 为 max(dp, dp] + nums)。
[*]判断结果：假如 dp 等于 target，则说明存在一种分割方式，使得两个子集的和相等，返回 true；否则返回 false。
以下是实现该解法的代码：
class Solution {
public boolean canPartition(int[] nums) {
int target = 0;
for(int i=0;i<nums.length;i++){
target = target + nums;
}
if(target % 2 != 0) return false;
target = target/2;
int[] dp = new int;
for(int i =0;i< nums.length;i++){
for(int j=target;j>=nums;j--){
dp = Math.max(dp,dp]+nums);
}
}
if(dp == target){
return true;
}else {
return false;
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]