网站设计计费,怎样建设直播网站,做游戏网站年入百万,百度推广查询背包类别
01背包#xff1a;有n种物品#xff0c;每种物品只有一个. 完全背包#xff1a;有n种物品#xff0c;每种物品有无限个. 多重背包#xff1a;有n种物品#xff0c;每种物品个数各不相同. 区别#xff1a;仅仅体现在物品个数上的不同而已。
确定dp[i][j]数组的…背包类别
01背包有n种物品每种物品只有一个. 完全背包有n种物品每种物品有无限个. 多重背包有n种物品每种物品个数各不相同. 区别仅仅体现在物品个数上的不同而已。
确定dp[i][j]数组的含义[0,i]的物品任取放容量为j的背包里.
LeetCode:1049. 最后一块石头的重量 II 1049. 最后一块石头的重量 II - 力扣LeetCode 1.思路
01背包问题dp[n 1]初始化大小之所以是 n 1 在于 n 是一个最大容量且数组下标从 0 开始。 遍历顺序先遍历物品再遍历背包后者背包倒序是为了将物品大值先放入背包保证每个物品只能遍历一次。 递推公式取决于物品大小和背包容量如果背包容量 物品大小则允许放入此时背包状态dp[j - stones[i]] stones[i]否则不允许放入此时背包状态dp[j],选择两者之中的较大值即可。
2.代码实现 1// 一维似乎更好理解2class Solution {3 public int lastStoneWeightII(int[] stones) {4 int sum 0;5 for (int num : stones) {6 sum num;7 }8 int target sum / 2;9 int[] dp new int[target 1];
10 for (int i 0; i stones.length; i) {
11 for (int j target; j stones[i]; j--) {
12 dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);
13 }
14 }
15 return sum - 2 * dp[target];
16 }
17}3.复杂度分析
时间复杂度O(n^2). 空间复杂度O(n).
LeetCode: 494. 目标和
494. 目标和 - 力扣LeetCode 1.思路
本题可以抽象成01背包问题中间需要计算一下… 遍历顺序依旧是先物品再背包保证物品先放入最大值及元素的唯一性. 分两种情况sum0时,取绝对值之后进入遍历.
2.代码实现 1class Solution {2 public int findTargetSumWays(int[] nums, int target) {3 int sum 0;4 for (int num : nums) {5 sum num;6 }7 if (target 0 sum -target) return 0;8 if ((target sum) % 2 ! 0) return 0;9 int size (target sum) / 2;
10 if (size 0) size -size;
11
12 int[] dp new int[size 1];
13 dp[0] 1;
14 for (int i 0; i nums.length; i) {
15 for (int j size; j nums[i]; j--) {
16 dp[j] dp[j - nums[i]];
17 }
18 }
19 return dp[size];
20 }
21}3.复杂度分析
时间复杂度O(n^2). 空间复杂度O(n).
LeetCode: 474.一和零
474. 一和零 - 力扣LeetCode
1.思路
拆解将m和n共同看作背包的整体字符串中每个元素看成物品。沿用上述遍历顺序和dp[][]数组定义输出即可.
2.代码实现 1class Solution {2 public int findMaxForm(String[] strs, int m, int n) {3 // dp[i][j] 表示i个0 和 j个1时的最大子集数4 int[][] dp new int[m 1][n 1];5 int one;6 int zero;7 // 先遍历物品8 for (String str : strs) {9 one 0;
10 zero 0;
11 // 得出每个字符串元素中包含的0和1的个数
12 for (char ch : str.toCharArray()) {
13 if (ch 0) {
14 zero;
15 } else {
16 one;
17 }
18 }
19 // 倒序遍历背包保证每个字符串元素只会被用一次
20 for (int i m; i zero; i--) {
21 for (int j n; j one; j--) {
22 dp[i][j] Math.max(dp[i][j], dp[i - zero][j - one] 1);
23 }
24 }
25 }
26 return dp[m][n];
27 }
28}3.复杂度分析
时间复杂度O(kmn). 空间复杂度O(mn).
