最后一块石头的重量 II

力扣题目链接
思路：尽可能分成重量相似的两堆，碰撞后剩下的重量最小

var lastStoneWeightII = function(stones) {
    let n=stones.length//物品
    let sum=stones.reduce((p,c)=>p+c,0)
    let volumn= Math.floor(sum/2)

    let dp=new Array(volumn+1).fill(0)

    for(let i=0;i<n;i++){
        for(let j=volumn;j>=stones[i];j--){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i])
        }
    }

    return sum-dp[volumn] -dp[volumn]
};

目标和

力扣题目链接
分析：背包问题的应用
其实是求装满有几种方法，是一个组合问题。
转换为背包问题：
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法。

1. dp数组含义：装满容量为j（包括j）的包，有dp[j]种方法
2. 递推公式：dp[j] += dp[j - nums[i]]
   (补充：所以求组合类问题的公式，都是类似这种递推公式）
3. 初始化：
   dp[0]=1
   例如：需带入例子。数组[0] ，target = 0，那么 bagSize = (target + sum) / 2 = 0

var findTargetSumWays = function(nums, target) {
    let sum=nums.reduce((p,c)=>p+c)
    if(Math.abs(target) > sum) {
        return 0;
    }

    if((target + sum) % 2) {
        return 0;
    }
    
    let bagSize= Math.floor((sum+target)/2)
    let dp=new Array(bagSize+1).fill(0)
    dp[0]=1

    for(let i=0;i<nums.length;i++){
        for(let j=bagSize;j>=nums[i];j--){
            dp[j] += dp[j-nums[i]]
        }
    }
    return dp[bagSize]
};

一和零

力扣题目链接
本质：装满背包有多少物品。

1. dp数组含义：(需要定义二维数组)。dp[i][j] 装满i个0，j个1 最多有dp[i][j]个子集。
2. 确定递推公式：dp[i][j]=Math.max(dp[i][j],dp[i-x][j-y]+1)
3. 初始值：
   dp[i][0]=0。（以保证之后的递推时，值不会被初始值覆盖掉）
4. 遍历顺序：
   先遍历物品，后遍历背包。背包倒序遍历

var findMaxForm = function(strs, m, n) {
    // 背包容量二维
    let dp=new Array(m+1).fill(0).map(ele=>{
        return new Array(n+1).fill(0)
    })

    for(let str=0;str<strs.length;str++){
        // 统计每一次的0和1的个数
        let x=0
        let y=0
        for(let k in strs[str]){
            if(strs[str][k]==='0'){
                x++
            }else{
                y++
            }
        }

        for(let i=m;i>=x;i--){
            for(let j=n;j>=y;j--){
                dp[i][j]=Math.max(dp[i][j],dp[i-x][j-y]+1)
            }
        }
    }
    return dp[m][n]
};