详解动态规划01背包问题--JavaScript实现

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

详解动态规划01背包问题--JavaScript实现对其他动态规划问题感兴趣的，也可以查看⼀开始在接触动态规划的时候，可能会云⾥雾⾥，似乎能理解思路，但是⼜⽆法准确地表述或者把代码写出来。本篇将⼀步⼀步通过作图的⽅式帮助初次接触动态规划的同学来理解问题。这⼀篇将以经典的 01背包 问题为例⼦来讲解，最后通过纯 JavaScript 来实现，在Sublime 上运⾏演⽰。当然如果不会 JavaScript 也⼀点关系都没有，因为最重要的是理解整个推导过程。在语⾔实现的时候，也没有涉及什么语⾔特性，基本上懂个C语⾔就能看懂了。问题给定⼀个固定⼤⼩的背包，背包的容量为 capacity，有⼀组物品，存在对应的价值和重量，要求找出⼀个最佳的解决⽅案，使得装⼊背包的物品总重量不超过背包容量 capacity，⽽且总价值最⼤。本题中给出了3个物品，其价值和重量分别是 (3,2),(4,3),(5,4)。括号左边为价值，右边为重量，背包容量 capacity 为5。那么求出其搭配组合，使得背包内总价最⼤，且最⼤价值为多少？分析在开始计算之前，需要先对动态规划中的01背包问题有基本的理解：物品⽆法拆成分数形式，如果能拆分，那就属于贪婪算法问题，在后⾯的⽂章我们也会介绍贪婪算法。不⼀定恰好装满背包。装满时总价值不⼀定最⼤。每样物品各⼀件常规情况下，在表格中，价格和重量⼀般都是从上到下递增的。我们填表分析的时候，其实是事先默认了这种递增的关系。清楚了上⾯的原则之后，就可以开始进⾏分析了。 当⼀个新物品出现的时候，需要去决策如果选择了它，是否会让总价值最⼤化。我们根据问题，建⽴如下表格⽤于分析：

我们对这个表格做⼀下说明，左上⾓ val 和 w 分别是物品的价值和重量。即上⾯所描述的3个物品的价值与重量对应关系。从第三列到最后⼀列，使⽤了变量 j，它表⽰背包总容量，最⼤值为5，也就是前⾯问题所说的 capacity 的值。第⼆⾏到最后⼀⾏，使⽤ i 表⽰，下标从0开始，⼀共有3个物品，所以 i 的最⼤值为 2。即我们使⽤i表⽰物品，在下⾯介绍中将i=0称为物品0，i=1称为物品1，以此类推。除了 j = 0 的情况以外，我们将从左到右，从上到下⼀步⼀步去填写这个表格，来找到最⼤的价值。表格中未填写的空格，表⽰背包内物品总价值。我们后⾯将使⽤ T[i][j] ⼆维数组来表⽰它。1. 总容量为0的情况如果背包总容量为0，那么很显然地，任何物品都⽆法装进背包，那么背包内总价值必然是0。所以第⼀步先填满 j=0 的情况。2. 第0⾏，i = 0 的空格分析正如上⾯所说，我们接下来将从上到下，从左往右地填写这个表格。所以现在把注意⼒定位到 i =0, j = 1 的空格上。在分析过程中，有⼀个重要原则：分析第i⾏时，它的物品组合仅能是⼩于等于i的情况。怎么理解这个原则：⽐如分析i=0这⼀⾏,那么背包⾥只能装⼊物品0，不能装⼊其他物品。分析i=1这⼀⾏，物品组合可以是物品0和物品1i=0 j=1 : 背包总容量为1，但是物品0 的重量为 2，⽆法装下去，所以这⼀格应该填

0。i=0 j=2 : 背包总容量为2，刚好可以装下物品0 ，由于物品0 的价值为3，因此这⼀格填 3。i=0 j=3 : 背包总容量为3，由于根据上⾯说明的物品组合原则，第0⾏，仅能放物品0，不需要考虑物品1 和 物品2，所以这⼀格填 3。i=0 j=4 : 同理，填 3 。i=0 j=5 : 同理，填 3 。这样我们可以完成第0⾏的填写，如下图：

3. 第1⾏，i = 1 的空格分析在这⼀⾏，可以由物品0 和物品1 进⾏⾃由组合，来装⼊背包。 i=1 j=1 : 背包总容量为1，但是物品0 的重量为 2，物品1重量为3，背包⽆法装下任何物品，所以填 0。i=1 j=2 : 背包总容量为2，只能装下物品0，所以填 3。i=1 j=3 : 背包总容量为3，这时候可以装下⼀个物品1，或者⼀个物品0，仅仅从⼈⼯填表的⽅式，很容易理解要选择物品1，但是我们该如何以⼀个确切的逻辑来表达，让计算机明⽩呢？基于上⾯说说明的价值和重量在表格中从上到下递增原则，可以确认物品1的价值是⼤于物品0的，所以默认情况下优先考虑物品1，当选择了物品1之后，把背包剩余的容量和物品1之前的物品重量对⽐（也就是和物品0的重量对⽐，如果剩余重量能装下前⾯的物品，那么就继续装）。所以这⾥选择物品1，填 4i=1 j=4 : 选择了物品1之后，物品1 的重量为3，背包容量为4， 减去物品1的重量后， 剩余容量为1，⽆法装下物品0，所以这⾥填 4i=1 j=5 选择了物品1之后，剩余的容量为2，刚好可以装下物品0，所以⼀格背包装了物品1，和物品 0，总价值为7，把 7 填⼊表格。这样我们就完成了第⼆⾏的填写，如下图：

3. 第2⾏，i = 2 的空格分析i=2 j=1 : 填 0 。i=2 j=2 : 填写这⼀⾏时，3种物品都有机会被装⼊背包。总容量为2时，只能装物品0，所以填 3。i=2 j=3 : 物品2的重量为4，⼤于容量j，所以这⾥可以参考 T[i-1][j]的值，也就是 i=1 j=3那⼀格的值，填 4。i=2 j=4 : 可以装下物品2，价值为5。也可以装下物品1。这⼀空格需要谨慎⼀点。我们将使⽤更严谨的⽅式来分析。在i=1 j=5 中出现了物品组合⼀起装⼊背包的情况，这⼀空将延续这种分析⽅式。我们选择了物品2，剩余的容量表达式应为 j-w[i] 即 4 - 4 = 0，剩余的容量⽤于上⼀⾏的搜索，由于上⼀⾏我们是填写完的，所以可以很轻易地得到这个值。表达式可以写成 val[i] + T[i-1][j-w[i]] ，可以根据这个表达式得出⼀个值。但是这并不是最终结果，还需要和上⼀⾏同⼀列数值对⽐，即 T[i-1][j]，对⽐，取最⼤值。最后这⾥填 5。i=2 j=5 : 根据上⾯计算原理，这⾥如果选择了物品2，那么最⼤价值只能5，参照上⼀⾏，同⼀列，价值为7，取最⼤值。所以放弃物品2，选择将物品0和物品1装⼊背包，填写7。完成后的表格如下：

伪代码表达理解了上⾯整个填表过程，我们要把逻辑抽取出来，在具体代码实现之前，先⽤伪代码表达出来。if(j < w[i]){ //容量⼩于重量，hold不住 T[i][j] = T[i-1][j]; //所以值等于上⼀⾏，同⼀列。如果i=0,没有上⼀⾏，则T[i][j] 取0}else{ T[i][j] = max(val[i] + T[i-1][j-w[i]] , T[i-1][j]); //参照上⾯ i=2 j=4 和 i=2 j=5 时的填表分析}复制代码以上这简短的伪代码就是解决问题的核⼼思路，可以应⽤于任何你熟悉的编程语⾔上。说到这⾥，这篇⽂章应该是要基本告⼀段落了。JavaScript 实现如果你已经理解了上⾯的填表分析和伪代码表达，那么就可以尝试着⾃⼰去⽤代码实现了。最后放出在使⽤ JavaScript的⼀种实现⽅式供⼤家参考，不再针对针对代码做太多说明，重要区域会有注释。如果 Sublime ⽀持纯 JavaScript，可以直接复制黏贴，command+b 运⾏看结果。function knapSack(w,val,capacity,n){ var T = [] for(let i = 0;i < n;i++){ T[i] = []; for(let j=0;j <= capacity;j++){ if(j === 0){ //容量为0 T[i][j] = 0; continue; }

if(j < w[i]){ //容量⼩于物品重量，本⾏hold不住 if(i === 0){ T[i][j] = 0; // i = 0时，不存在i-1，所以T[i][j]取0 }else{ T[i][j] = T[i-1][j]; //容量⼩于物品重量，参照上⼀⾏ } continue; } if(i === 0){ T[i][j] = val[i]; //第0⾏，不存在 i-1, 最多只能放这⼀⾏的那⼀个物品 }else{ T[i][j] = (val[i] + T[i-1][j-w[i]],T[i-1][j]); } } } findValue(w,val,capacity,n,T); return T;}//找到需要的物品function findValue(w,val,capacity,n,T){ var i = n-1, j = capacity; while ( i > 0 && j > 0 ){ if(T[i][j] != T[i-1][j]){ ('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]); j = j- w[i]; i--; }else{ i--; //如果相等，那么就到 i-1 ⾏ } } if(i == 0 ){ if(T[i][j] != 0){ //那么第⼀⾏的物品也可以取 ('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]); } }}// w = [2,3,4]. val = [3,4,5] , n = 3 , capacity = 5//function knapSack([2,3,4],[3,4,5],5,3);//

var values = [3,4,5], weights = [2,3,4], capacity = 5, n = ;(knapSack(weights,values,capacity,n));复制代码输出结果

空间优化代码：作者：YinTokey链接：/post/6844963来源：掘⾦著作权归作者所有。商业转载请联系作者获得授权，⾮商业转载请注明出处。

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

详解动态规划01背包问题--JavaScript实现对其他动态规划问题感兴趣的，也可以查看⼀开始在接触动态规划的时候，可能会云⾥雾⾥，似乎能理解思路，但是⼜⽆法准确地表述或者把代码写出来。本篇将⼀步⼀步通过作图的⽅式帮助初次接触动态规划的同学来理解问题。这⼀篇将以经典的 01背包 问题为例⼦来讲解，最后通过纯 JavaScript 来实现，在Sublime 上运⾏演⽰。当然如果不会 JavaScript 也⼀点关系都没有，因为最重要的是理解整个推导过程。在语⾔实现的时候，也没有涉及什么语⾔特性，基本上懂个C语⾔就能看懂了。问题给定⼀个固定⼤⼩的背包，背包的容量为 capacity，有⼀组物品，存在对应的价值和重量，要求找出⼀个最佳的解决⽅案，使得装⼊背包的物品总重量不超过背包容量 capacity，⽽且总价值最⼤。本题中给出了3个物品，其价值和重量分别是 (3,2),(4,3),(5,4)。括号左边为价值，右边为重量，背包容量 capacity 为5。那么求出其搭配组合，使得背包内总价最⼤，且最⼤价值为多少？分析在开始计算之前，需要先对动态规划中的01背包问题有基本的理解：物品⽆法拆成分数形式，如果能拆分，那就属于贪婪算法问题，在后⾯的⽂章我们也会介绍贪婪算法。不⼀定恰好装满背包。装满时总价值不⼀定最⼤。每样物品各⼀件常规情况下，在表格中，价格和重量⼀般都是从上到下递增的。我们填表分析的时候，其实是事先默认了这种递增的关系。清楚了上⾯的原则之后，就可以开始进⾏分析了。 当⼀个新物品出现的时候，需要去决策如果选择了它，是否会让总价值最⼤化。我们根据问题，建⽴如下表格⽤于分析：

我们对这个表格做⼀下说明，左上⾓ val 和 w 分别是物品的价值和重量。即上⾯所描述的3个物品的价值与重量对应关系。从第三列到最后⼀列，使⽤了变量 j，它表⽰背包总容量，最⼤值为5，也就是前⾯问题所说的 capacity 的值。第⼆⾏到最后⼀⾏，使⽤ i 表⽰，下标从0开始，⼀共有3个物品，所以 i 的最⼤值为 2。即我们使⽤i表⽰物品，在下⾯介绍中将i=0称为物品0，i=1称为物品1，以此类推。除了 j = 0 的情况以外，我们将从左到右，从上到下⼀步⼀步去填写这个表格，来找到最⼤的价值。表格中未填写的空格，表⽰背包内物品总价值。我们后⾯将使⽤ T[i][j] ⼆维数组来表⽰它。1. 总容量为0的情况如果背包总容量为0，那么很显然地，任何物品都⽆法装进背包，那么背包内总价值必然是0。所以第⼀步先填满 j=0 的情况。2. 第0⾏，i = 0 的空格分析正如上⾯所说，我们接下来将从上到下，从左往右地填写这个表格。所以现在把注意⼒定位到 i =0, j = 1 的空格上。在分析过程中，有⼀个重要原则：分析第i⾏时，它的物品组合仅能是⼩于等于i的情况。怎么理解这个原则：⽐如分析i=0这⼀⾏,那么背包⾥只能装⼊物品0，不能装⼊其他物品。分析i=1这⼀⾏，物品组合可以是物品0和物品1i=0 j=1 : 背包总容量为1，但是物品0 的重量为 2，⽆法装下去，所以这⼀格应该填

0。i=0 j=2 : 背包总容量为2，刚好可以装下物品0 ，由于物品0 的价值为3，因此这⼀格填 3。i=0 j=3 : 背包总容量为3，由于根据上⾯说明的物品组合原则，第0⾏，仅能放物品0，不需要考虑物品1 和 物品2，所以这⼀格填 3。i=0 j=4 : 同理，填 3 。i=0 j=5 : 同理，填 3 。这样我们可以完成第0⾏的填写，如下图：

3. 第1⾏，i = 1 的空格分析在这⼀⾏，可以由物品0 和物品1 进⾏⾃由组合，来装⼊背包。 i=1 j=1 : 背包总容量为1，但是物品0 的重量为 2，物品1重量为3，背包⽆法装下任何物品，所以填 0。i=1 j=2 : 背包总容量为2，只能装下物品0，所以填 3。i=1 j=3 : 背包总容量为3，这时候可以装下⼀个物品1，或者⼀个物品0，仅仅从⼈⼯填表的⽅式，很容易理解要选择物品1，但是我们该如何以⼀个确切的逻辑来表达，让计算机明⽩呢？基于上⾯说说明的价值和重量在表格中从上到下递增原则，可以确认物品1的价值是⼤于物品0的，所以默认情况下优先考虑物品1，当选择了物品1之后，把背包剩余的容量和物品1之前的物品重量对⽐（也就是和物品0的重量对⽐，如果剩余重量能装下前⾯的物品，那么就继续装）。所以这⾥选择物品1，填 4i=1 j=4 : 选择了物品1之后，物品1 的重量为3，背包容量为4， 减去物品1的重量后， 剩余容量为1，⽆法装下物品0，所以这⾥填 4i=1 j=5 选择了物品1之后，剩余的容量为2，刚好可以装下物品0，所以⼀格背包装了物品1，和物品 0，总价值为7，把 7 填⼊表格。这样我们就完成了第⼆⾏的填写，如下图：

3. 第2⾏，i = 2 的空格分析i=2 j=1 : 填 0 。i=2 j=2 : 填写这⼀⾏时，3种物品都有机会被装⼊背包。总容量为2时，只能装物品0，所以填 3。i=2 j=3 : 物品2的重量为4，⼤于容量j，所以这⾥可以参考 T[i-1][j]的值，也就是 i=1 j=3那⼀格的值，填 4。i=2 j=4 : 可以装下物品2，价值为5。也可以装下物品1。这⼀空格需要谨慎⼀点。我们将使⽤更严谨的⽅式来分析。在i=1 j=5 中出现了物品组合⼀起装⼊背包的情况，这⼀空将延续这种分析⽅式。我们选择了物品2，剩余的容量表达式应为 j-w[i] 即 4 - 4 = 0，剩余的容量⽤于上⼀⾏的搜索，由于上⼀⾏我们是填写完的，所以可以很轻易地得到这个值。表达式可以写成 val[i] + T[i-1][j-w[i]] ，可以根据这个表达式得出⼀个值。但是这并不是最终结果，还需要和上⼀⾏同⼀列数值对⽐，即 T[i-1][j]，对⽐，取最⼤值。最后这⾥填 5。i=2 j=5 : 根据上⾯计算原理，这⾥如果选择了物品2，那么最⼤价值只能5，参照上⼀⾏，同⼀列，价值为7，取最⼤值。所以放弃物品2，选择将物品0和物品1装⼊背包，填写7。完成后的表格如下：

伪代码表达理解了上⾯整个填表过程，我们要把逻辑抽取出来，在具体代码实现之前，先⽤伪代码表达出来。if(j < w[i]){ //容量⼩于重量，hold不住 T[i][j] = T[i-1][j]; //所以值等于上⼀⾏，同⼀列。如果i=0,没有上⼀⾏，则T[i][j] 取0}else{ T[i][j] = max(val[i] + T[i-1][j-w[i]] , T[i-1][j]); //参照上⾯ i=2 j=4 和 i=2 j=5 时的填表分析}复制代码以上这简短的伪代码就是解决问题的核⼼思路，可以应⽤于任何你熟悉的编程语⾔上。说到这⾥，这篇⽂章应该是要基本告⼀段落了。JavaScript 实现如果你已经理解了上⾯的填表分析和伪代码表达，那么就可以尝试着⾃⼰去⽤代码实现了。最后放出在使⽤ JavaScript的⼀种实现⽅式供⼤家参考，不再针对针对代码做太多说明，重要区域会有注释。如果 Sublime ⽀持纯 JavaScript，可以直接复制黏贴，command+b 运⾏看结果。function knapSack(w,val,capacity,n){ var T = [] for(let i = 0;i < n;i++){ T[i] = []; for(let j=0;j <= capacity;j++){ if(j === 0){ //容量为0 T[i][j] = 0; continue; }

if(j < w[i]){ //容量⼩于物品重量，本⾏hold不住 if(i === 0){ T[i][j] = 0; // i = 0时，不存在i-1，所以T[i][j]取0 }else{ T[i][j] = T[i-1][j]; //容量⼩于物品重量，参照上⼀⾏ } continue; } if(i === 0){ T[i][j] = val[i]; //第0⾏，不存在 i-1, 最多只能放这⼀⾏的那⼀个物品 }else{ T[i][j] = (val[i] + T[i-1][j-w[i]],T[i-1][j]); } } } findValue(w,val,capacity,n,T); return T;}//找到需要的物品function findValue(w,val,capacity,n,T){ var i = n-1, j = capacity; while ( i > 0 && j > 0 ){ if(T[i][j] != T[i-1][j]){ ('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]); j = j- w[i]; i--; }else{ i--; //如果相等，那么就到 i-1 ⾏ } } if(i == 0 ){ if(T[i][j] != 0){ //那么第⼀⾏的物品也可以取 ('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]); } }}// w = [2,3,4]. val = [3,4,5] , n = 3 , capacity = 5//function knapSack([2,3,4],[3,4,5],5,3);//

var values = [3,4,5], weights = [2,3,4], capacity = 5, n = ;(knapSack(weights,values,capacity,n));复制代码输出结果

空间优化代码：作者：YinTokey链接：/post/6844963来源：掘⾦著作权归作者所有。商业转载请联系作者获得授权，⾮商业转载请注明出处。