0-1 袋子问题
主题描述
Ming 是一位科学家,他需要参加一个重要的国际科学会议来展示他的最新研究成果。他需要带一些研究资料,但他的行李箱空间有限。这些研究资料包括实验设备、文献、实验样本等,各自占据不同的空间,具有不同的价值。
Ming的行李空间为N。问Ming应该如何选择携带最有价值的研究资料。每个研究材料只能选择一次,并且只有选择或不选择两种选择,并且不能进行裁剪。
输入描述
第一行包含两个正整数,第一个整数M代表研究材料的类型,第二个正整数N代表Ming的行李空间。
第二行包含 M 个正整数,代表每种研究材料占用的空间。
第三行包含M个正整数,代表每个研究材料的价值。
输出描述
输出一个整数,代表Ming可以携带的研究材料的最大值。
输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示
小明可以携带6个研究材料,但行李空间只有1个,而占用1个空间的研究材料价值5个,所以最终答案是输出5。
数据范围:
1
1
研究材料占用空间和研究材料价值均小于等于1000。
公开课主{
公共静态无效主(字符串[]参数){
/ 代码 /
扫描仪 s = new Scanner(System.in);
int M = s.nextInt();
int N = s.nextInt();
// 清除缓冲区符号 /n
s.nextLine();
字符串 w = s.nextLine();
字符串 v = s.nextLine();
int[] 权重 = Arrays.stream(w.split(" "))
.mapToInt(整数::valueOf)
.toArray();
int[] value = Arrays.stream(v.split(" "))
.mapToInt(整数::valueOf)
.toArray();
int[][] dp = 新 int[M][N+1];
for(int i=权重[0]; i j){
dp[i][j] = dp[i-1][j];
}别的{
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 权重[i]] + 值[i]);
}
}
}
System.out.println(dp[M-1][N]);
}
}
登录后复制
1,dp数组意味着我们可以获得item i和目标bag size j的最大值。行表示物品,列表示包的尺寸。
2,对于init,我们初始化第一行和第一列(但实际上我们默认初始化列为0,这意味着)
3,回归关系为:对于每一项:
a、如果物品的重量大于包的尺寸,则无法选择该物品,当前尺寸为之前选择的物品集合的尺寸。
b、如果物品的重量可以,我们必须比较之前选择的物品的集合的大小减去当前物品的大小(如果我们不这样做,则总大小将是大小 + 大小当前项目的,它将破坏我们的 dp 数组的逻辑)。
这里,是双循环的顺序,因为我们可以用一个二维数组来记录所有结果,从上一行开始查找当前行。
另外,我们可以使用一维数组来实现。
for(int i=1; i
dp[i][j] = dp[i-1][j];
}别的{
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 权重[i]] + 值[i]);
}
改成
int[] dp = new int[target+1];
登录后复制
for(int i=1; i
if(nums[i] > j){
继续;
}
dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
}
}
</nums.length>登录后复制
416. 划分子集和相等
给定一个整数数组 nums,如果可以将数组划分为两个子集,使得两个子集中的元素之和相等,则返回 true,否则返回 false。
示例1:
输入:nums = [1,5,11,5]
输出:true
说明:数组可以分为 [1, 5, 5] 和 [11]。
示例2:
输入:nums = [1,2,3,5]
输出:假
说明:数组不能划分为等和子集。
限制:
1
1
原始页面
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
如果(总和%2==1){
返回假;
}
int 目标=总和>>1;
int[][] dp = new int[nums.length][目标+1];
for(int i=nums[0]; i j){
dp[i][j] = dp[i-1][j];
}别的{
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
}
}
}
返回 dp[nums.length-1][目标] == 目标;
}
登录后复制以上就是LeetCode Day动态编程第31部分的详细内容,更多请关注php中文网其它相关文章!
91资源网站长-冰晨2024-08-27 17:15
发表在:【账号直充】爱奇艺黄金VIP会员『1个月』官方直充丨立即到账丨24小时全天秒单!不错不错,价格比官方便宜
91资源网站长-冰晨2024-08-27 16:15
发表在:2022零基础Java入门视频课程不错,学习一下