题解 | #数组分组#

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];

  }
  }