代码随想录算法训练营Day35|动态规划Part03|01背包问题 二维、01背包问题 一维、416. 分割等和子集

01背包问题 二维（关键）

代码随想录

视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

背包最大重量为4。

物品为：

问背包能背的物品最大价值是多少？

public class Bag { public static void main(String[] args) { int[] weights = {1,3,4}; int[] values = {15,20,30}; int[][] dp = new int[3][5]; for(int i=0;i<3;i++){ dp[i][0] = 0; } for(int j=0;j=weights[0] ? values[0]:0; } for(int m=1;m<3;m++){ for(int n=1;n=weights[m]){  dp[m][n] = Math.max(dp[m-1][n], dp[m-1][n-weights[m]]+values[m]); } else{  dp[m][n] = dp[m-1][n]; } } } printdp(dp); } public static void printdp(int[][] dp){ int row = dp.length; int column = dp[0].length; for(int i=0;i<row;i++){ for(int j=0;j<column;j++){ System.out.print(dp[i][j]); System.out.print(\' \'); } System.out.println(); } }}

01背包问题 一维(关键)

代码随想录

视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

public class Bag { public static void main(String[] args) { int[] weights = {1,3,4}; int[] values = {15,20,30}; int[] dp = new int[5]; for(int i=0;i=weights[i];j--){ dp[j] = Math.max(dp[j], dp[j-weights[i]]+values[i]); } } printdp(dp); } public static void printdp(int[] dp){ int column = dp.length; for(int j=0;j<column;j++){ System.out.print(dp[j]); System.out.print(\' \'); } System.out.println(); }}

416. 分割等和子集(关键)

代码随想录

视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

• 输入: [1, 5, 11, 5]
• 输出: true
• 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

• 输入: [1, 2, 3, 5]
• 输出: false
• 解释: 数组不能分割成两个元素和相等的子集.

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

思路

错误写法：左右指针遍历直到相邻，判断左侧和与右侧和是否相等。（1，1，2，2）是一个反例，和不一定非要从一侧取。

import java.util.Arrays;class Solution { public boolean canPartition(int[] nums) { Arrays.sort(nums); int left = 0; int right = nums.length-1; if(left == right) return false; int sumleft = nums[left]; int sumright = nums[right]; while(left<right-1){ if(sumleftsumright) sumright+=nums[--right]; } return sumleft==sumright ? true:false; }}

class Solution { public boolean canPartition(int[] nums) { //using 2-D DP array. int len = nums.length; //check edge cases; if(len == 0) return false; int sum = 0; for (int num : nums) sum += num; //we only deal with even numbers. If sum is odd, return false; if(sum % 2 == 1) return false; int target = sum / 2; int[][] dp = new int[nums.length][target + 1]; // for(int j = 0; j <= target; j++){ // if(j < nums[0]) // dp[0][j] = 0; // else // dp[0][j] = nums[0]; // } //initialize dp array for(int j = nums[0]; j <= target; j++){ dp[0][j] = nums[0]; } for(int i = 1; i < len; i++){ for(int j = 0; j <= target; j++){ if (j < nums[i])  dp[i][j] = dp[i - 1][j]; else  dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]); } } //print out DP array // for(int x : dp){ // System.out.print(x + \",\"); // } // System.out.print(\" \"+i+\" row\"+\"\\n\"); return dp[len - 1][target] == target; }}