SOURCE

function fillMostValueInBag (weights, values, count, totalWeight) {
    let dp = new Array(count + 1)
    for (let i = 0; i < count + 1; i ++) {
        dp[i] = new Array(totalWeight + 1)
        for (let j = 0; j < totalWeight+1; j ++) {
            if(i == 0 || j == 0) {
                dp[i][j] = 0
            } else {
                if(j-weights[i-1] < 0) {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = Math.max( dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] )
                }
            }
            console.log('dp['+i+']['+j+']='+dp[i][j])
        }
    }   
    let ret = dp[count][totalWeight]
    console.log(ret) 
    return ret
}

let ws = [2,3,4,1]
let vals = [5,2,6,3] 
// fillMostValueInBag(ws, vals, 4, 6)



// 给定一组数，能否分成两个和相等的子集
// [1,2,4,1] true ([1,2,1] [4])
// [1,4,7,5] false 
//

function canPartition(nums) {
    let sum = 0
    for (let num in nums) {
        sum += nums[num]
    }
    // console.log(sum)
    if(sum%2) {
        console.log("Odds")
        return false
    } 
    sum = sum/2
    let dp = new Array(nums.length + 1)
    for (let i = 0; i < nums.length + 1; i ++) {
        dp[i] = new Array(sum + 1)
        for(let j = 0; j <= sum; j ++) {
            if(j == 0) dp[i][j] = true 
            else if (i == 0) dp[i][j] = false
            else {
                if (j < nums[i])  { 
                    dp[i][j] = dp[i-1][j]
                } else if(j == nums[i]) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
                }
            }
        }
    }
    if(dp[nums.length][sum]) {
        console.log("YES on [" + nums + "]")
        return true
    }
}


canPartition([1,2,4,1])

///////////////////////////////////////////////////////////////////////////
///
///
function canBePartioned(nums) {
    let sum = 0
    for(let num in nums) {
        sum += nums[num]
    }
    if(sum%2) {
        console.log("Odds")
        return false
    }
    sum = sum/2
    let dp = new Array(sum + 1)
    dp[0] = true
    for(let i = 0; i < nums.length; i ++) {
        for(let j = sum; j > 0; j --) {
            if(j < nums[i]) {
                break
            } else if (j == nums[i]) {
                dp[j] = true
            } else {
                dp[j] = dp[j-nums[i]]
            }
        }
        if (dp[sum]) {
            console.log("YES on [" + nums + "]")
            return true
        }
    }
    return false
}

canBePartioned([1,2,4,1,3,2,1])

// 完全背包问题
// 无限数量的一堆零钱，有多少种方法凑出给定的总数
//

function methodsCountForMount(coins, amount) {
    let dp = new Array(coins.length +1)
    for(let i = 0; i < coins.length+1; i ++) {
        dp[i] = new Array(amount + 1) 
        for (let j = 0; j < amount + 1; j ++) {
            if (i == 0 && j != 0) {
                dp[i][j] = 0
            } else if (j == 0) {
                dp[i][j] = 1
            } else {
                if (j < coins[i-1]) {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]] 
                }
            }
            // console.log('dp['+i+']['+j+']='+dp[i][j])
        }
    }
    // console.log('dp = ' + dp)
    let count = dp[coins.length][amount]
    console.log(count + " methods to amount " + amount)
}

methodsCountForMount([1,2,5], 3)

///// 
/////
function methodsCountForMountCompress(coins, amount) {
    let dp = new Array(amount + 1) 
    dp[0] = 1
    for(let i = 0; i < coins.length; i ++) {
        for (let j = 1; j <= amount; j ++) {
            if (j >= coins[i]) {
                if(dp[j]==null) {
                    console.log('dp[j] = ' + dp[j])
                    dp[j] = 0
                }
                if(dp[j-coins[i]]==null) {
                    console.log('dp[j-coins[i-1]] = ' + dp[j-coins[i]])
                    dp[j-coins[i]] = 0
                } 
                dp[j] = dp[j] + dp[j-coins[i]] 
            }
        }
    }
    console.log('dp = ' + dp)
    let count = dp[amount]
    console.log(count + " methods to amount " + amount)
}

methodsCountForMountCompress([1,2,5], 3)