H5W3
当前位置:H5W3 > 其他技术问题 > 正文

【Web前端问题】动态规划——把一个整数数组分成两个和相等的子集,怎么写

当数组nums=[2,3,5]时,测试通过,但当nums=[5,3,2]时,测试就不能通过,这是为什么?

window.onload = function() {
    //nums = [3,2,5];
    nums=[5,3,2];
    console.log("****************"+canPartition(nums))
}
var canPartition = function(nums) {
    var totleSum = 0;
    var minNums = Math.min.apply(null, nums);
    for (var i = 0; i < nums.length; i++) totleSum += nums[i];
    if (totleSum % 2 !== 0) return false;
    var target = totleSum / 2;
    var len = nums.length;
    var value = nums;
    var dp = new Array();
    var str = [];
            for (var i = 0; i < len; i++) {
                // dp[i] = new Array();
                dp[i] = [];
            }

    for (var i = nums[0]; i <= target; i++) {
        dp[0][i] =value[0];
        console.log(dp[0][i]);
    } 
   
    console.log("----------------");

    for (var i = 1; i < len; i++) {
        str = [];
        for (var j = target; j >=nums[i] ; j--) {
            var q =  dp[i - 1][j];
            if(q === NaN || q === undefined) 
            console.log("j:" + j + "   " +"i-1:"+(i-1)+"   "+ "nums[i]:" + nums[i] + "   " + "dp[i-1][j]:" + dp[i - 1][j]);
            var x = dp[i - 1][j - nums[i]];
            if (x === undefined || x === NaN){ x=0;
            console.log("j:" + j + "   " +"i-1:"+(i-1)+"   "+ "nums[i]:" + nums[i] + "   " + "dp[i-1][j-nums[i]] + value[i]:" + z);}
            var y = value[i];
            var z = x + y;
            dp[i][j] = Math.max(q, z);
            console.log(dp[i][j]);
        }
    }
if (dp[len - 1][target] === target) return true;
else return false;

};

本文地址:H5W3 » 【Web前端问题】动态规划——把一个整数数组分成两个和相等的子集,怎么写

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址