农场的奶牛分组

[编程题]农场的奶牛分组

热度指数：476 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

农场里有一群奶牛，每头奶牛都有自己的体重。农场主想把奶牛分成两组，使得两组奶牛的体重和相等。你能帮他完成这个任务吗？

示例1

输入

[10,20,30,20]

输出

true

说明

可以将奶牛分成两组，一组的体重是[20, 20]，另一组的体重是[10, 30]。

示例2

输入

[10,20,30,50]

输出

false

备注:

1 <= weights.length <= 200
1 <= weights[i] <= 100

算法知识视频讲解

Sylva_Lin

子集背包

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

        if(sum % 2) return false;

        int n = weights.size();
        sum = sum / 2;

        vector<vector<bool>> dp(n+1, vector<bool>(sum+1));
        for(int i = 0; i <= n; i++){
            dp[i][0] = true;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= sum; j++){
                if(j - weights[i-1] < 0){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - weights[i-1]];
                }
            }
        }

        return dp[n][sum];
    }
};

发表于 2024-08-18 16:55:23 回复(0)

伦纳德西装革履版

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型一维数组 
     * @return bool布尔型
     */
    public boolean canPartition (int[] weights) {
        // write code here
        int sum = Arrays.stream(weights).sum();
        if (sum % 2 != 0) {
            return false;
        }
        int halfSum = sum/2;
        int[] nums = Arrays.stream(weights).filter(a -> a <= halfSum).toArray();
        int[] dp = new int[halfSum+1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = halfSum; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
                if (dp[j] == halfSum) {
                    return true;
                }
            }
        }
        return false;
    }
}

发表于 2024-05-19 14:36:32 回复(0)