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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @return bool布尔型
     */
    public boolean canPartition (int[] weights) {
        // write code here
        int sum = 0;
        for (int weight : weights) {
            sum += weight;
        }

        if ((sum & 1) == 1) {
            return false;
        }

        sum >>= 1;
        boolean[] f = new boolean[sum + 1];
        f[0] = true;

        for (int weight : weights) {
            for (int j = sum; j >= weight; j--) {
                f[j] = f[j] || f[j - weight];
            }
        }

        return f[sum];
    }
}

编程语言是Java

考察的知识点为动态规划

代码解释：计算数组中所有元素的和，如果和为奇数，则无法平分为两个相等的子集，直接返回 false。然后，将总和除以 2，目标是在数组中找到一个子集的和等于这个值。使用一个布尔数组 f 来记录当前和能否由数组中的一部分元素组成，初始化只有 f[0] 为 true。然后，遍历数组中的每个元素，从后往前更新布尔数组，如果当前和可以由之前的元素和组成，或者加入当前元素后能够达到当前和，就将对应的 f 值设置为 true。最后，返回布尔数组的 f[sum] 位置即可判断是否可以平分为两个子集。