Day42 动态规划 part04

Day42 动态规划 part04

46. 携带研究材料(卡哥的卡码网的题目)

背包问题

我的思路:
写不了一点儿…T^T
总结规律就是，dp数组要比原来各个size + 1，dp[i][j] = Math.max(xxx, xxxx（根据题目情况进行各种处理）)

解答：

import java.util.*;public class Main {public static void main (String[] args) {Scanner myScanner = new Scanner(System.in);int goodSize = myScanner.nextInt();int bagSize = myScanner.nextInt();int[] weight = new int[goodSize];int[] value = new int[goodSize];for(int i = 0; i < goodSize; i++) {weight[i] = myScanner.nextInt();}for(int i = 0; i < goodSize; i++) {value[i] = myScanner.nextInt();}BagProblem(weight, value, bagSize);}public static void BagProblem(int[] weight, int[] value, int bagSize) {int[][] dp = new int[weight.length + 1][bagSize + 1];for(int i = 1; i < dp.length; i++) {for(int j = 1; j < dp[0].length; j++) {if(j < weight[i - 1]) {dp[i][j] = dp[i - 1][j];}else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);}}}System.out.println(dp[dp.length - 1][bagSize]);}
}

416. 分割等和子集

我的思路：
笑死，已经学会抢答了！！
不管怎么样，模板是一把子背住了

		int[] dp = new int[xxx+ 1];for(int i = 0; i < dp.length; i++) {for(int j = xxx; j < xxx; j++) {dp[j] = Math.max(xxx, xxx);}}

题解思路应该是，数组之和的一半sum(nums)/2，dp数组是长度为 sum(nums)/2 + 1（总结规律，size + 1），从后向前（不一样了）不断比较并且更新最大值，如果dp数组最后一个值 == sum(nums)/2，那么就说明可以划分成两个和相等的子集

解答：

class Solution {public boolean canPartition(int[] nums) {int sum = Arrays.stream(nums).sum();if(sum % 2 != 0) {return false;}int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < nums.length; i++) {for(int j = dp.length - 1; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}if(target == dp[target]) {return true;}}return target == dp[target];}
}