完全背包理論基礎(chǔ)

0-1背包 與 完全背包的區(qū)別：
0-1背包：一個(gè)物品只能拿一次
完全背包：一個(gè)物品可以拿多次

完全背包遞推公式跟01背包一直。但遍歷順序不為逆序，而是正序遍歷（正序遍歷可以實(shí)現(xiàn)某個(gè)物品取多次）。

function maxValue(weight, value, bagWeight) {
  let dp = new Array(bagWeight + 1).fill(0); //初始化

  for (let i = 0; i < weight.length; i++) {
    //物品
    for (let j = weight[i]; j <= bagWeight; j++) {
      //背包
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
    console.log(dp);
  }
  return dp[bagWeight];
}

maxValue([1, 3, 4], [15, 20, 30], 4);
// dp數(shù)組打?。?// [ 0, 15, 30, 45, 60 ]
// [ 0, 15, 30, 45, 60 ]
// [ 0, 15, 30, 45, 60 ]

零錢兌換

本質(zhì)：完全背包的應(yīng)用。裝滿一個(gè)背包有多少種方法（與之前求目標(biāo)和類似，但是目標(biāo)和的物品只能選擇一次）
力扣題目鏈接

1. 含義及遞推公式
   dp[j] 裝滿背包j，有dp[j]種方法
   dp[j] += dp[j - coins[i]];
   2.正序遍歷（因?yàn)橥晃锲房梢匀《啻危?/li>

var change = function(amount, coins) {
    let dp = new Array(amount + 1).fill(0); //初始化
    dp[0] = 1;

    for (let i = 0; i < coins.length; i++) {
        //物品
        for (let j = coins[i]; j <= amount; j++) {
        //背包
        dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
};

組合總和

leecode題目鏈接
與零錢兌換的區(qū)別：
本題強(qiáng)調(diào)元素的順序，零錢兌換不強(qiáng)調(diào)元素順序。

遍歷順序若為先物品，后背包：得到組合數(shù)
先物品，后背包：得到排列數(shù)

var combinationSum4 = function(nums, target) {
    let dp = new Array(target + 1).fill(0); //初始化
    dp[0] = 1;

    for (let i = 0; i <= target; i++) {
        //背包
        for (let j = 0; j < nums.length; j++) {
            //物品
            if (i - nums[j] >= 0) {
                dp[i] += dp[i - nums[j]];
            }
        }
        console.log(dp);
    }

    console.log(dp[target]);
    return dp[target];
};