农场里有一群奶牛,每头奶牛都有自己的体重。农场主想把奶牛分成两组,使得两组奶牛的体重和相等。你能帮他完成这个任务吗?
农场里有一群奶牛,每头奶牛都有自己的体重。农场主想把奶牛分成两组,使得两组奶牛的体重和相等。你能帮他完成这个任务吗?
[10,20,30,20]
true
可以将奶牛分成两组,一组的体重是[20, 20],另一组的体重是[10, 30]。
[10,20,30,50]
false
1 <= weights.length <= 200
1 <= weights[i] <= 100
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; } }