题解 | #农场的奶牛分组#

先求得奶牛的总体重sum，然后找到一个目标值target，使得分成两组的奶牛体重和都等于target。

首先，我们需要检查是否满足可以将奶牛分成两组的条件。如果奶牛的总数小于2，或者总体重不能被2整除，那么无法分成两组，直接返回false。

然后，我们可以定义一个二维数组dp，dp[i][j]表示在前i头奶牛中是否存在一个分组，使得体重之和等于j。

初始状态为dp[0][0] = true，表示前0头奶牛的体重之和为0，是成立的。

接下来，我们可以进行动态规划的转移。对于第i头奶牛，我们有两种选择：将其加入一个组，或者不加入组。如果加入组，那么相应的状态变化为dp[i][j] = dp[i-1][j-weight[i]](前i头牛的状态=前i-1头牛在(体重=j-第i头牛的体重)的状态)，

其中weight[i]表示第i头奶牛的体重。如果不加入任何组，状态保持不变，即dp[i][j] = dp[i-1][j]。

最终，我们需要检查dp[n][target]是否为true，其中n为奶牛数量

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param weights int整型一维数组
     * @return bool布尔型
     */
    public boolean canPartition (int[] weights) {
        // write code here
        int n = weights.length;
        int sum = Arrays.stream(weights).sum();
        // 无法分为两组
        if (n < 2 || sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        // dp[i][j]表示在前i头奶牛中是否存在一个分组,使得体重之和为j
        boolean[][] dp = new boolean[n + 1][target + 1];
        // 表示前0头牛的体重之和为0可以分组
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                // 第i头牛不加入分组
                dp[i][j] = dp[i - 1][j];// 与上一次保持一致
                if (j >= weights[i - 1]) {// 第i头牛的体重<=j<=target
                    // 加入分组,状态=dp[i-1][j-weights[i-1]](前i-1头牛在(j-当前牛的体重)的分组状态)
                    dp[i][j] |= dp[i - 1][j - weights[i - 1]];
                }
            }
        }
        return dp[n][target];
    }
}

计算整个数组的元素和。如果和为奇数，那么无法分为两个和相等的子集，因此返回false。

然后，要将问题转换为是否存在一个子集，使得它的和等于整个数组的和的一半，也就是target。

使用动态规划的方法来解决这个问题。定义一个布尔数组dp，其中dp[i]表示是否存在一个子集的和等于i。初始时，设置dp[0]为true，因为和为0的子集总是存在的。

接下来，遍历整个weights数组。对于数组中的每个元素weight，从target开始逆序更新dp数组。如果dp[i-weight]为true，那么说明存在一个子集的和等于i-weight，那么将dp[i]设置为true。

最后，返回dp[target]的值，表示是否存在一个子集的和等于target。

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @return bool布尔型
     */
    public boolean canPartition (int[] weights) {
        // write code here
        int n = weights.length;
        int sum = Arrays.stream(weights).sum();
        // 无法分为两组
        if (n < 2 || sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        // 是否存在一组的和=i
        boolean[] dp = new boolean[target + 1];
        // 和为0的子集存在
        dp[0] = true;
        for(int weight:weights){
            // 若dp[i-weight]==true,则dp[i]=true
            // i<weight时,和为i的子集不存在
            for(int i=target;i>=weight;--i){
                dp[i] |= dp[i-weight];
            }
        }
        return dp[target];
    }
}