背包问题是经典的动态规划问题，一共分为9类。

• 01背包问题
• 完全背包问题
• 多重背包问题
• 混合背包问题
• 二维费用背包问题
• 分组背包问题
• 背包问题求方案书
• 求背包问题的方案
• 有依赖的背包问题 前提条件： 有 n 个物品和容量为 V 的背包，第 i 件物品的体积为 c[i]，价值为 w[i]。现在的目标是确定要将哪些物体放入背包，以保证在体积 不超过背包容量 的前提下，背包内的 总价值最高？

1、01背包问题

约束条件：每种物品数量是1，可以选择放或者不放。

状态转移方程 状态定义：f[i][v]是前 i 个物品中，体积恰好是 v时的最大值。

f[i][v]=Math.max(f[i-1][v],f[i-1][v-c[i]]+w[i])

• 不选第 i 个物品，那么前 i 个物品的最大价值就是 i-1个物品的价值。则状态转移方程为 f[i][v]=f[i-1][v]。
• 选择了第i个物品，那么前 i-1个物品的体积就是 v-c[i],那么状态转移方程是f[i][v]=f[i-1][v-c[i]]+w[i]。

状态转移方程优化 将二维数组转化为一维数组。

f[v]=Math.max(f[v],f[v-c[i]]+w[i])

例题-leetcode 322题 -零钱兑换 (opens new window)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

const coinChange =(coins, amount)=> {
    //一维数组
    const dp=[0].concat(new Array(amount+1).fill(Infinity));
    //先循环总金额
    for(let i=1;i<=amount;i++){
        //循环面额
        for(let j=0;j<coins.length;j++){
            if(i>=coins[j]){
                //实例是是在求Math.min(dp[i-1]+1,dp[i])
                dp[i]=Math.min(dp[i],dp[i-coins[j]]+1)
            } 
        }
    }
    return dp[amount]===Infinity?-1:dp[amount]
};

2、完全背包问题

约束条件：每种物品的数量为无限个，你可以选择任何数量的物品。

状态转移方程 状态定义：f[i][v]为前 i 种物品中，体积恰好为 v 时的最大价值。

f[i][v] = max(f[i-1][v-k*c[i]] + k*w[i]), 0 <=k*c[i]<=v //k表示选择k次

例题 面试题 08.11. 硬币 (opens new window)

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

var waysToChange = function(n) {
    let dp = new Array(n+1).fill(1)
    let coins = [1,5,10,25]
    const mod=1e9+7;
    for(let i=1; i<4; i++){
        for(let j=coins[i]; j<=n; j++){
            // dp[j]表示n由n个1组成这种组合方式
            // dp[i-coins[i]]表示 n-coins[i]剩下的都是由1组成
            //当n=5时，有两种组合方式
            //当n=10时,有四种组合方式
            dp[j] = (dp[j]+dp[j-coins[i]]) % mod
           
        }
    }
    return dp[n]
};