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

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 经典的 0-1 背包问题，即将 n 个物品放入容量为 W 的背包中，每个物品有一个体积和一个价值，要求选出若干个物品，使得它们的体积之和不超过背包容量，而它们的价值之和最大。
2. 可以将奶牛的体重看作物品的体积和价值相等。具体而言，我们可以定义一个二维布尔数组 dp，其中 dp[i][j] 表示从前 i 头奶牛中选取若干头，它们的体重之和是否恰好为 j。根据以上分析，我们有如下动态规划转移方程：dp[i][j]=dp[i−1][j] or dp[i−1][j−weight[i]], 其中 weight[i] 表示第 i 头奶牛的体重。如果不选取第 i 头奶牛，则 dp[i][j] 取决于前 i-1 头奶牛是否能够凑出体重和为 j；如果选取第 i 头奶牛，则 dp[i][j] 取决于前 i-1 头奶牛是否能够凑出体重和为 j-weight[i]。
3. 最终答案为 dp[n][sum/2]，其中 sum 是所有奶牛的体重之和。注意到如果 sum 不是偶数，则无法将奶牛分成两组体重相等的部分，此时直接返回 False。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param weights int整型一维数组
# @return bool布尔型
#
class Solution:
    def canPartition(self, weights: List[int]) -> bool:
        n, total = len(weights), sum(weights)
        if total % 2 != 0:
            return False
        target = total // 2
        dp = [[False] * (target + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = True
        for i in range(1, n + 1):
            for j in range(1, target + 1):
                if j >= weights[i - 1]:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - weights[i - 1]]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[n][target]