平顶山网站开发,专业做互联网招聘的网站有哪些,wordpress模板自适应修改,建设工程管理条例Day42 动态规划 part04
46. 携带研究材料(卡哥的卡码网的题目)
背包问题
我的思路: 写不了一点儿…T^T 总结规律就是#xff0c;dp数组要比原来各个size 1#xff0c;dp[i][j] Math.max(xxx, xxxx#xff08;根据题目情况进行各种处理#xff09;)
解答#xff1a; …Day42 动态规划 part04
46. 携带研究材料(卡哥的卡码网的题目)
背包问题
我的思路: 写不了一点儿…T^T 总结规律就是dp数组要比原来各个size 1dp[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)/2dp数组是长度为 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];}
}
