题解 | #数组分组#

package 华为.动态规划01;

import java.util.Scanner;

1.先将数组中3的倍数与5的倍数的数字分别相加并计算他们之间的差值
sum3:3的倍数数字相加之和 sum5：5的倍数数字相加之和
value = sum3-sum5
2.计算剩余数字的和sum
3.判断sum能否分为差值为value的两组数组
<==>sum = sum - value,判断判断剩余的数组+value能否分为和相等的两组数组
<==>target = sum/2,判断剩余的数组+value中能否找到若干个数来填充满容积为target的背包(以下的计算方法看leetcode之分割等和子集)
(注意这儿数组是带负数的，所以我们要讲剩余的数组中的数和value转化为正数，这样才和leetcode之分割等和子集完全类似)

/
public class 数组分组 {
public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);
  while(sc.hasNext()){
      //输入数据个数
      int n = sc.nextInt();
      //输入数据
      int[] nums = new int[n];
      for (int i = 0; i < n; i++) {
          nums[i] = sc.nextInt();
      }
      //判断能否分为相等的两个数组
      System.out.println(canPartition(nums));
  }

}

private static boolean canPartition(int[] nums) {

  int len = nums.length;
  //1.先将数组中3的倍数与5的倍数的数字分别相加并计算他们之间的差值
  //2.计算剩余数字的和sum
  int[] newNums = new int[2*len];
  int sum3 = 0;
  int sum5 = 0;
  int sum = 0;
  int count = 0;
  int maxValue = Integer.MIN_VALUE;
  for (int i = 0; i < len; i++) {
      if (nums[i]%3==0) {
          sum3 = sum3 + nums[i];
      }else if (nums[i]%5==0){
          sum5 = sum5 + nums[i];
      }else{
          if(nums[i]<0){//负数变正数
              nums[i] = -nums[i];
          }
          sum = sum + nums[i];
          newNums[count] = nums[i];
          maxValue = nums[i]>=maxValue ? nums[i]:maxValue;
          count = count + 1;
      }
  }
  int value = sum3-sum5;//计算差值
  if (value<0) {
      value = -value;
  }
  //3.判断剩余的数组+value中能否找到若干个数来填充满容积为target的背包
  newNums[count] = value;
  sum = sum + value;
  //判断能否提前退出
  if (count==0) {
      return true;
  }
  if(sum%2!=0){
      return false;
  }
  int target = sum/2;
  if (maxValue>target) {
      return false;
  }
  //递归
  boolean[][] dp = new boolean[count][target+1];
  //边界值
  dp[0][newNums[0]] = true;
  for (int i = 0; i < count; i++) {
      dp[i][0] = true;
  }
  for (int i = 1; i < count; i++) {
      for (int j = 1; j <= target; j++) {
          if (newNums[i]>j) {
              dp[i][j] = dp[i-1][j];
          }else if(newNums[i]<=j){
              dp[i][j] = dp[i-1][j] || dp[i-1][j-newNums[i]];
          }
      }
  }
  return dp[count-1][target];

}
}