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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。

题目考察的知识点

动态规划

题目解答方法的文字分析

这是一个经典的0-1背包问题，我们可以使用动态规划的方法来解决。

首先，计算所有奶牛的体重总和totalWeight，然后判断totalWeight是否为偶数，如果不是偶数，那么无法将奶牛分成两组体重和相等的情况，直接返回false。

接下来，我们要求解的是能否在weights中找到一个子集，使得它们的体重和等于totalWeight的一半，即问题转化为背包问题。我们定义一个二维数组dp，其中dp[i][j]表示前i个奶牛中是否存在一组奶牛，使得它们的体重和恰好等于j。dp[i][j]为true表示存在，dp[i][j]为false表示不存在。

接下来，我们考虑状态转移方程。对于第i个奶牛，它的体重是weights[i]，我们有两种选择：选取它放入子集中，或者不选取它。如果选取它放入子集中，那么问题就转化为是否存在前i-1个奶牛的一个子集，使得它们的体重和等于j-weights[i]；如果不选取它，问题就转化为是否存在前i-1个奶牛的一个子集，使得它们的体重和等于j。因此，状态转移方程为：dp[i][j] = dp[i-1][j] || dp[i-1][j - weights[i]];

最后，我们可以从dp[n][totalWeight/2]中得到答案，其中n是奶牛的数量。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 保存每头奶牛的体重
     * @return bool布尔型 表示能否将奶牛分成两组体重和相等
     */
    bool canPartition(vector<int>& weights) {
        int n = weights.size(); // 获取奶牛的数量
        int totalWeight = 0; // 计算奶牛的体重总和

        // 计算所有奶牛的体重总和
        for (int i = 0; i < n; i++) {
            totalWeight += weights[i];
        }

        // 如果总体重为奇数，则无法将奶牛分成两组体重和相等的情况，直接返回false
        if (totalWeight % 2 != 0) {
            return false;
        }

        totalWeight /= 2; // 计算两组奶牛体重和的目标值，即totalWeight的一半

        vector<vector<bool>> dp(n + 1, vector<bool>(totalWeight + 1, false));

        // 基本情况：对于任意的i，dp[i][0]都为true，因为总是可以找到一个空的子集，其体重和为0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // 填充dp数组，使用状态转移方程
        // dp[i][j] = dp[i-1][j] || dp[i-1][j - weights[i]];
        // dp[i][j]表示前i个奶牛中是否存在一组奶牛，使得它们的体重和等于j
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= totalWeight; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选取第i个奶牛
                if (j >= weights[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - weights[i - 1]]; // 选取第i个奶牛
                }
            }
        }

        // 返回dp数组的最后一个元素，即从起始位置到最后一个奶牛的体重和为totalWeight的子集是否存在
        return dp[n][totalWeight];
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！