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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型一维数组 
     * @return bool布尔型
     */
    public boolean canPartition (int[] weights) {
        // write code here
        if (weights == null || weights.length < 2) return false;
        // 能不能凑出奶牛体重是总体重一半的牛
        int total_weight = 0;
        for (int i = 0; i < weights.length; i++) {
            total_weight += weights[i];
        }
        if (total_weight % 2 != 0) {
            return false;
        }
        total_weight /= weights.length;// total_weight代表我们要凑出的和
        boolean[][] dp = new boolean[weights.length + 1][total_weight + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = true;
        }
        for (int j = 1; j < dp[0].length; j++) {
            for (int i = dp.length - 2; i >= 0; i--) {
                if (j - weights[i] >= 0) {
                    dp[i][j] = dp[i + 1][j - weights[i]] || dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][total_weight];
        // return canPartition(weights, total_weight, 0);
    }
    // 递归解法
    public boolean canPartition(int[] arr, int target, int index) {
        if (index == arr.length) {
            return target == 0 ? true : false;
        }
        if (target - arr[index] >= 0) {
            return canPartition(arr, target - arr[index], index + 1) || 
                canPartition(arr, target, index + 1);
        }
        return canPartition(arr, target, index + 1);
    }
}

描述

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

分析

就是找农场中所有牛体重总和的一半（记为target），实际上就是找数组中是否能凑出这个target

思路

• 采用递归进行选择，选择有两种：
• 一种是使用index索引处的元素
• 第二种是不使用index索引处的元素
• 直到index指向数组的末端，这时候看是否target为0
• 如果为0，说明可以凑出target
• 如果不为0，说明不能凑出target

递归转动态规划

由于上面提到的递归之后两个可变参数，所以我们使用一个二维数组进行接收，两个可变参数的范围分别是0-length和0-target。

然后根据递归的的过程从左到右再从下到上遍历数组，最后就可以得到结果。