题解 | #牛能和牛可乐的礼物#

方法1 暴力求解

看到题目第一想法，每个礼物选或者不选有两条分支。因为我们希望尽量把礼物均分，所以要求累计价值不超出总价值的一半，否则将执行剪枝。如果出现正好均分的方案后，将flag置1，跳过后续遍历分支的步骤。当所有分支走完，找一个总价值最接近一半的方案。

很遗憾，暴力求解的方案虽然已经做了一定的剪枝操作，但在数据量多了之后仍会超时，用例通过69.23%。

function maxPresent( presentVec ) {
    let all = eval(presentVec.join("+"))
    let max =0
    let flag = 0
    choose(presentVec,0,0)
    function choose(presentVec,i,sum){
        if(flag==1)return
        if(i<presentVec.length){
            choose(presentVec,i+1,sum)
            if((sum+presentVec[i])<=all/2){
                choose(presentVec,i+1,sum+presentVec[i])
                max = Math.max(max,sum+presentVec[i])
                if(max==all/2){
                    flag=1
                    return
                }
            }
        }
    }
    return Math.abs(all-2*max)
}
module.exports = {
    maxPresent : maxPresent
};

方法2 动态规划

结合暴力破解的思路，每一个礼物选或者不选，其实很像0/1背包问题。现在的背包空间变成了总价值的一半，我们目标是尽量放满背包，使得总价值量最大。题目备注中的“单个礼物价值不超过100，礼物个数小于100，所有礼物总价值不超过10000”其实也在引导我们使用dp数组进行解题。

新手做动态规划的题目最迷茫的就是，我们应该怎样使用dp数组？或者说我们需要用dp数组的每一个空间表示什么样的含义？

我们可以用dp表示，最多只能拿i价值的礼物，实际拿到的最多的礼物价值dp[i].这样我们可以再利用每个物品的价值，去建立dp空间之间的联系。

例如[1,2,3,4]，总价值量sum为10，因为希望尽量均分，所以我们只用开0-5的对应数组[0,0,0,0,0,0]，其中dp[5]就表示最多拿价值和为5的礼物组合，实际能拿到的最大价值量。

我们顺着每个礼物来看，引入第一件礼物（价值为1）时，dp就变成了[0,1,1,1,1,1]，表示可拿价值上限大于等于1时，实际最大价值量都为这第一件物品的价值。

引入第二件物品（价值为2）时，dp就变成了[0,1,2,3,3,3],表示可拿价值上限大于等于1时，实际价值最多为1；可拿价值上限大于等于2时，实际价值最多为2；可拿价值上限大于等于3时，实际价值最多为3（因为目前我们只引入了两件礼品）

引入第三件物品（价值为3）时，dp就变成了[0,1,2,3,4,4]

引入第四件物品（价值为4）时，dp就变成了[0,1,2,3,4,5]

最终差值即为总价值量sum-2*dp数组的最后一位

function maxPresent( presentVec ) {
    if(presentVec.length==0)   return 0
    let sum = eval(presentVec.join('+'))
    let dp = new Array(Math.floor(sum/2)+1).fill(0)
    //dp[i]表示设定价值总量上限i时，实际能获得的最大物品价值总量，
    //因为我们希望尽量均分，所以只需要开一半总量的dp空间
    //比如实例1[1,2,3,4]，sum为10，我们需要开0-5也就是6个空间的dp
    for(let i = 0;i<presentVec.length;i++){
        for(let j = dp.length-1;j>=presentVec[i];j--){
            dp[j]=Math.max(dp[j],dp[j-presentVec[i]]+presentVec[i])
            //对于每一个presentVec中的物品，我们调整价值总量上限大于等于这个物品价值的dp空间，否则总量不够也加不进来
            //比较dp[j]和dp[j-presentVec[i]]+presentVec[i]，选择价值量更大的组合
        }
    }
    return sum-2*dp[dp.length-1]
}
module.exports = {
    maxPresent : maxPresent
};