文章目录
- 卡码网 46. 携带研究材料(第六期模拟笔试)
- 解题思路
- 代码
- 总结
- Leetcode 416. 分割等和子集
- 解题思路
- 代码
- 总结
草稿图网站
java的Deque
卡码网 46. 携带研究材料(第六期模拟笔试)
题目:46. 携带研究材料(第六期模拟笔试)
解析:代码随想录解析
解题思路
每行代表不同的物品,每列代表背包的重量,先放完第一个物品,再放第二个物品,以此类推。
代码
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int[] weight = new int[M];
int[] values = new int[M];
for (int i = 0; i < M; i++)
weight[i] = sc.nextInt();
for (int i = 0; i < M; i++)
values[i] = sc.nextInt();
int [][]dp = new int[M][N+1];
//初始化
for (int i = weight[0]; i <= N; i++)
dp[0][i] = values[0];
for (int i = 1; i < M; i++) //物品
for (int j = 0; j <= N; j++) { //重量
if (weight[i] > j) //如果物品的重量大于容量
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i]] + values[i]);
}
System.out.println(dp[M-1][N]);
}
}
//滚动数组
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int[] weight = new int[M];
int[] values = new int[M];
for (int i = 0; i < M; i++)
weight[i] = sc.nextInt();
for (int i = 0; i < M; i++)
values[i] = sc.nextInt();
int []dp = new int[N+1];
//初始化
for (int i = weight[0]; i <= N; i++)
dp[i] = values[0];
for (int i = 1; i < M; i++) //物品
for (int j = N; j >= weight[i]; j--) { //重量
dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]);
}
System.out.println(dp[N]);
}
}
总结
Leetcode 416. 分割等和子集
题目:416. 分割等和子集
解析:代码随想录解析
解题思路
因为数组的个数和值有限制,所以使用辅助数组作为滚动数组,进行动规。如果sum为奇数则返回false,否则寻找是否有和为sum / 2的组合。也就是容量为sum / 2的背包是否能包含sum / 2的价值的东西。
代码
class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0)
return false;
int sum = 0;
for (int i = 0; i < nums.length; i++)
sum += nums[i];
if (sum % 2 == 1)
return false;
int target = sum / 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;
}
return dp[target] == target;
}
}
总结
暂无