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

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 = 0;
        for (int i = 0; i < n; i++) {
            sum += weights[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= target; i++) {
            if (weights[0] == i) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= target; j++) {
                if (weights[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - weights[i]];
                }
            }
        }
        return dp[n - 1][target];
    }
    }

该代码使用的编程语言是Java。

题目是一个经典的背包问题，也可以理解为0-1背包问题的变形。给定一个整数数组，判断是否能将数组分割成两个子集，使得两个子集的元素和相等。

代码通过动态规划来解决该问题。首先，计算整个数组的元素和sum。如果sum是奇数，则无法分割成两个和相等的子集，直接返回false。如果sum是偶数，则可以将问题转化为在数组中找到是否存在子集的和为sum/2。

使用一个二维布尔数组dp，dp[i][j]表示前i个元素中能否组合出和为j。初始化dp数组，将dp[i][0]设为true，表示前i个元素的子集和为0总是存在的；将dp[0][weights[0]]设为true，表示只有一个元素时如果与weights[0]相等则为true，否则为false。

然后，对于每个元素weights[i]，遍历所有的和j（从1到target），根据以下规则更新dp数组：

• 如果weights[i]大于j，则dp[i][j]等于dp[i-1][j]，表示不选择将weights[i]放入子集；
• 否则，dp[i][j]等于dp[i-1][j]（即不选择将weights[i]放入子集）或dp[i-1][j - weights[i]]（即选择将weights[i]放入子集）。

最后，返回dp[n-1][target]，其中n为数组长度，target为sum的一半。如果dp[n-1][target]为true，则存在子集的和为sum/2，返回true；否则，返回false。

这样，通过动态规划的方式，可以高效地解决该问题。