2023年8月1日发(作者：)

JS动态规划算法--01背包问题动态规划动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的⽅式去解决。01 背包问题有 N 件物品和⼀个容量为 V 的背包。第 i 件物品的体积是 c[i]，价值是 w[i]。求解将哪些物品装⼊背包可使价值总和最⼤（每⼀种物品只能放⼀次）分析解答也不多扯⽪，直⼊正题。先看⼀个简单的问题，斐波那契数列：dynFib(n) { let arr = new Array(n).fill(0); arr[0] = 1; arr[1] = 1; for (let i = 2; i < n; i++) { arr[i] = arr[i - 1] + arr[i - 2]; } // 返回最后⼀个 return arr[n - 1];}该问题就是⼀个简单的动态规划问题,关键点在于找到状态关系: f(n) = f(n-1) + f(n-2);回到背包问题，可以参考上⾯斐波那契数列的递推关系，假设现在背包容量为 10，有⼀个物品数组:const product = [ { weight: 2, value: 3}, { weight: 2, value: 6 }, { weight: 6, value: 5 }, { weight: 5, value: 4 }, { weight: 4, value: 6 },];如果背包容量为 0，那么什么也放不下如果背包容量为 1，还是什么也放不下如果背包容量为 2，有两个物品都为质量都为 2，该放哪⼀个呢？这时需要做⼀个决策，先放物品 1，此时价值为 3；此时⽐较 上⼀个决策的价值 - 物品 1 的价值 + 放物品 2 的价值 和物品 1 的价值⽐，取⼤的当做该容量下的最优解⽤状态⽅程描述为： f[i][j]= (f[i-1][j],f[i-1][j]-c[i]]+w[i]); 其中 i 为第 i 件物品（0 开始）, j 为当前背包容量如果背包容量为 3，.............直到背包容量为 10，得到此时的最优解初始化⼀个⼆维矩阵来记录背包和价值的关系: = [];const row = ;const col = ty;for (let i = 0; i < row; i++) { [i] = new Array(col + 1).fill(0);}我们会发现，每⼀个状态都依赖于上⼀个状态，第⼀个物品需要⽐较没有物品的状态做⽐较，我们需要对 i=0 时做特殊处理，还有⼀个更巧妙的⽅法，初始化⼀个 -1 的状态:[-1] = new Array(col + 1).fill(0);如下图，我们发现类似于填表的⽅式，右下⾓即为背包最⼤容量时的价值;观察下表可以发现，该矩阵记录了每⼀个容量即状态的最优解，⽐如容量 7 时的最优解，我们可以找到 7 那⼀列最下⾯即 12;主函数部分,利⽤状态⽅程进⾏最优决策，calculate() { const row = ; const col = ty; let product; for (let i = 0; i < row; i++) { for (let j = 0; j < col + 1; j++) { product = t[i]; if (j < ) { [i][j] = [i - 1][j]; } else { [i][j] = ( [i - 1][j], [i - 1][j - ] + ); } } } delete [-1]; return [row - 1][col];}动态规划解决问题主要是两个:拆分、划分问题到某个颗度时，我们可以很轻易的做出决策确定状态⽅程，⽐如上⾯的: f[i][j]= (f[i-1][j],f[i-1][j]-c[i]]+w[i])源码源码END

2023年8月1日发(作者：)

JS动态规划算法--01背包问题动态规划动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的⽅式去解决。01 背包问题有 N 件物品和⼀个容量为 V 的背包。第 i 件物品的体积是 c[i]，价值是 w[i]。求解将哪些物品装⼊背包可使价值总和最⼤（每⼀种物品只能放⼀次）分析解答也不多扯⽪，直⼊正题。先看⼀个简单的问题，斐波那契数列：dynFib(n) { let arr = new Array(n).fill(0); arr[0] = 1; arr[1] = 1; for (let i = 2; i < n; i++) { arr[i] = arr[i - 1] + arr[i - 2]; } // 返回最后⼀个 return arr[n - 1];}该问题就是⼀个简单的动态规划问题,关键点在于找到状态关系: f(n) = f(n-1) + f(n-2);回到背包问题，可以参考上⾯斐波那契数列的递推关系，假设现在背包容量为 10，有⼀个物品数组:const product = [ { weight: 2, value: 3}, { weight: 2, value: 6 }, { weight: 6, value: 5 }, { weight: 5, value: 4 }, { weight: 4, value: 6 },];如果背包容量为 0，那么什么也放不下如果背包容量为 1，还是什么也放不下如果背包容量为 2，有两个物品都为质量都为 2，该放哪⼀个呢？这时需要做⼀个决策，先放物品 1，此时价值为 3；此时⽐较 上⼀个决策的价值 - 物品 1 的价值 + 放物品 2 的价值 和物品 1 的价值⽐，取⼤的当做该容量下的最优解⽤状态⽅程描述为： f[i][j]= (f[i-1][j],f[i-1][j]-c[i]]+w[i]); 其中 i 为第 i 件物品（0 开始）, j 为当前背包容量如果背包容量为 3，.............直到背包容量为 10，得到此时的最优解初始化⼀个⼆维矩阵来记录背包和价值的关系: = [];const row = ;const col = ty;for (let i = 0; i < row; i++) { [i] = new Array(col + 1).fill(0);}我们会发现，每⼀个状态都依赖于上⼀个状态，第⼀个物品需要⽐较没有物品的状态做⽐较，我们需要对 i=0 时做特殊处理，还有⼀个更巧妙的⽅法，初始化⼀个 -1 的状态:[-1] = new Array(col + 1).fill(0);如下图，我们发现类似于填表的⽅式，右下⾓即为背包最⼤容量时的价值;观察下表可以发现，该矩阵记录了每⼀个容量即状态的最优解，⽐如容量 7 时的最优解，我们可以找到 7 那⼀列最下⾯即 12;主函数部分,利⽤状态⽅程进⾏最优决策，calculate() { const row = ; const col = ty; let product; for (let i = 0; i < row; i++) { for (let j = 0; j < col + 1; j++) { product = t[i]; if (j < ) { [i][j] = [i - 1][j]; } else { [i][j] = ( [i - 1][j], [i - 1][j - ] + ); } } } delete [-1]; return [row - 1][col];}动态规划解决问题主要是两个:拆分、划分问题到某个颗度时，我们可以很轻易的做出决策确定状态⽅程，⽐如上⾯的: f[i][j]= (f[i-1][j],f[i-1][j]-c[i]]+w[i])源码源码END