农业交易平台网站建设,网站开发项目报价方案,网页设计简单,wordpress 搜索标签01背包问题 二维 dp[i][j] 表示在物品i时#xff0c;背包在j容量下的最大价值#xff0c;递推公式为 dp[i][j] Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] value[i]); 第一个时不放物品i#xff0c;其价值等于在物品i-1时背包在j容量下的最大价值#xff0c;第二个是放… 01背包问题 二维 dp[i][j] 表示在物品i时背包在j容量下的最大价值递推公式为 dp[i][j] Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] value[i]); 第一个时不放物品i其价值等于在物品i-1时背包在j容量下的最大价值第二个是放物品i表示是在i-1物品时背包在j-weight[i]时的价值加上i物品的价值。 public class BagProblem {public static void main(String[] args) {int[] weight {1,3,4};int[] value {15,20,30};int bagSize 4;testWeightBagProblem(weight,value,bagSize);}public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){int goods weight.length;int[][] dp new int[goods][bagSize 1];for (int j weight[0]; j bagSize; j) {dp[0][j] value[0];}for (int i 1; i weight.length; i) {for (int j 1; j bagSize; j) {if (j weight[i]) {dp[i][j] dp[i-1][j];} else {dp[i][j] Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] value[i]);}}}for (int i 0; i goods; i) {for (int j 0; j bagSize; j) {System.out.print(dp[i][j] \t);}System.out.println(\n);}}
} 01背包问题 一维 public static void main(String[] args) {int[] weight {1, 3, 4};int[] value {15, 20, 30};int bagWight 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen weight.length;//定义dp数组dp[j]表示背包容量为j时能获得的最大价值int[] dp new int[bagWeight 1];//遍历顺序先遍历物品再遍历背包容量for (int i 0; i wLen; i){for (int j bagWeight; j weight[i]; j--){dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}//打印dp数组for (int j 0; j bagWeight; j){System.out.print(dp[j] );}} 416. 分割等和子集 题目链接416. 分割等和子集 - 力扣LeetCode 思路;物品是nums[i]重量是nums[i]价值也是nums[i]背包体积是sum/2。 class Solution {public boolean canPartition(int[] nums) {if(nums null || nums.length 0) return false;int n nums.length;int sum 0;for(int num : nums) {sum num;}//总和为奇数不能平分if(sum % 2 ! 0) return false;int target sum / 2;int[] dp new int[target 1];for(int i 0; i n; i) {for(int j target; j nums[i]; j--) {//物品 i 的重量是 nums[i]其价值也是 nums[i]dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}//剪枝一下每一次完成內層的for-loop立即檢查是否dp[target] target優化時間複雜度26ms - 20msif(dp[target] target)return true;}return dp[target] target;}
}
