当前位置: 首页 > 图灵资讯 > 技术篇> LeetCode Day动态编程第31部分

LeetCode Day动态编程第31部分

来源:图灵教育
时间:2024-07-10 22:04:01

leetcode day动态编程第31部分

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<m i for j="1;" if> j){
		dp[i][j] = dp[i-1][j];
		}别的{
		dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 权重[i]] + 值[i]);
		}
</m>

改成

 int[] dp = new int[target+1];

 for(int i=1; i<nums.length i for j="目标;">=1; j--){
		if(nums[i] &gt; 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 目标=总和&gt;&gt;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][目标] == 目标;  
			}
	

以上是LeetCodede。 更多关于Day动态编程第31部分的详细信息,请关注图灵教育的其他相关文章!