01背包算法思想,背包算法 python

　　1.概述动态规划(DP)算法对于初学者来说是一个难点。在思考DP问题的时候，核心思想还是类似于其他算法，把复杂的问题分解成相对简单的问题。简单来说，问题规模为N的问题是否可以分解成N-1的问题(递归)？或者是否可以从音阶1推导出音阶n(递归和DP)。

　　背包算法是从1进制到n进制的典型算法，是最常见的DP算法。它的核心要素有三个：背包容量、物品重量(或体积)和物品价值。一般要求在背包容量的限制下获得最大值。最简单的背包问题是有n个物品，每个物品都有一个重量和值。背包空间有限的情况下如何选择物品实现价值最大化？

　　很明显，这种问题不是靠贪心的想法就能解决的。商品编号可以从1开始计算.n从第1条推断。(1)只有第1项。当背包足够大的时候，最大值就是物品1的价值。(2)取第2项。这个时候，如果背包空间足够大，显然你应该带上物品1和2。如果不够大，你就要做出取舍。(3)带物品3时，有四种前置状态：空袋、只有物品1、只有物品2、物品1、物品2。但如果这样处理，就变成了一个复杂度为2 n的搜索问题，搜索算法会计算出大量无效状态，效率极低。背包算法的巧妙之处在于，通过计算前I项在不同背包空间的最大值，避免了大量无效搜索，从而将复杂度降低到N 2。

　　背包的三要素可能有很多种形式，比如背包容量就是时间(以下题目都在洛古)(收药P1048)、体力(精卫填海P1510)、数值(最近似总和P1734)。重量和背包容量这两个概念在同一个题目里总是一致的。

　　背包有四种基本类型：01背包、完整背包、分组背包和多个背包。在此之上，还有针对背包容量升级的二次元背包(有两种不同的容量限制)，针对物品类型升级的混合背包(比如有的物品是01，有的物品是多个)，以及互相依赖的背包，比如你拿了B物品就必须拿a物品。

　　从笔者的经验来看，只要掌握01背包的二维写法，其他所有背包问题都可以用这个算法进行扩展。换句话说，所有背包问题都是01背包的拓展。比如依赖物品A和B(得到B必须得到A)可以想象成两个物品做01背包，一个是A，一个是(A B)。

　　二。01背包01背包意味着所有N件物品都是唯一的。每个项目我们只能选择或者不选择两个操作。01背包是所有其他背包问题的基础。换个思路，所有背包问题都可以用01背包的二维数组解法解决。背包的基本做法和其他动态规则差不多，每个循环完成一个物品的计算。二维数组dp[i][j]用来表示J背包容量的最大值或取第I项时的方案数。

　　就商品的价值而言，如果题目给出了价值或价值计算方法(P1060快乐金铭)，那么我们在写dp方程时就可以按题目要求添加。如果不赋予项目任何值，就让我们找到可以填充的最大容量或方案数。我们可以将dp数组的unit 0设置为1，dp[0]=1，方便推导出最大容量或方案数。

　　#包含位/标准数据。使用命名空间标准；int t，m，dp[105][1005]，ti[105]，val[105]；int main(){ int i，j；cintmfor(I=1；I=m；辛提瓦尔；for(I=1；I=m；I){ for(j=0；j=t；j){ if(jti[I])DP[I][j]=DP[I-1][j]；Else /** dp[i-1][j]不选择I项，dp[i-1][j-ti[i]] val[i]选择*/DP [I] [J]=Max (DP [I-1] [J]，DP[I-1]} } cout DP[m][t]；返回0；} 01背包问题充分体现了dp算法的特点，在计算第I行时只考虑第i-1行的值。01背包有一个优化技术，就是可以通过滚动数组来减少存储空间。此时，只需要一个一维数组就可以完成背包计算。学习这类算法，每次打印dp数组都能加深我们的理解。

　　#包含位/标准数据。使用命名空间标准；int t，m，dp[1005]，ti[105]，val[105]；int main(){ int i，j；cintmfor(I=1；I=m；辛提瓦尔；for(I=1；I=m；I )/**特别注意滚动的方向必须是从大到小*/for(j=t；j=ti[I]；J j - ) /** dp[j] [J]不选择I项，dp[j-ti[i]] val[i]选择I */DP [J]=Max (DP [J]，DP[J-Ti[I]]Val[I])；cout DP[t]；返回0；}三。完整背包和01背包问题完全类似，只是每个物品不限件。如果V是背包容量，C是物品重量，那么从每件物品来看，与之相关的策略不是拿或者不拿两种，而是拿0件，拿1件，拿2件.取[V/c]件等。如果还是按照解01背包的思路，每次还是可以用二维数组推导出一个物品的值，但是在推导第I个物品的值的时候，需要更新DP [I] [0].DP [I] [V]与0，1，2.[V/C]件依次进行，显然导致效率低下。这个问题可以通过滚动计算来解决。

　　#包含位/标准数据。使用命名空间标准；int i，j，T，M，t[101]，p[101]，DP[101][1001]；int main(){ scanf(%d%d ，T，M)；for(I=1；I=M；i ) scanf(%d%d ，t[i]，p[I])；for(I=1；I=M；I){ for(j=0；JT[I]；J) /**先取上一层的数据，作为不选I项的基础数据*/DP[I][j]=DP[I-1][j]；//对于数组在左上超出界限的位置(j=t[I])；j=T；J) /**滚动测试我取items */dp [i] [j]=max (dp [i-1] [j]，DP[I-1][j-t[I]]p[I])；} printf(%d ，f[M][T])；返回0；}对于背包问题的代码理解，个人建议每次背包计算后输出dp数组，观察dp数组变化的过程。从上面的代码可以明显看出，每次dp[i][j]都是先从dp[i-1][j]中取值，所以完全背包也可以使用一维数组滚动计算，这正好和01背包循环相反。

　　#包含位/标准数据。使用命名空间标准；int v，t，m，dp[100005]，ti[10005]，val[10005]；Int ()/* * p1616疯狂草药集*/{ int i，j；cintmfor(I=1；I=m；辛提瓦尔；for(I=1；I=m；I) /**为了实现1，2.t/ti物品，完整背包从小到大*/for(j=ti[I]；j=t；j ) dp[j]=max(dp[j]，DP[j-ti[I]]val[I])；cout DP[t]；返回0；} 4.分组背包分组背包和多个背包其实属于同一类问题，也可以看作是有条件的01背包(同一组只能选一个)。从理解问题的角度来看，二维dp数组是解决背包问题的万能钥匙。与上一个不同的是，同一组项被认为是一个项，有两个选择：01。Dp[i][j]代表背包容量为j时取第I组物品后的最大值，我们在计算dp[i][j]时，需要找到所有组号为I的物品分别尝试。

　　#包含位/标准数据。使用命名空间标准；/* *多合一1272:[例9.16]分组背包*/int v，n，t，a [1005]，b [1005]，c [1005]，f[15][205]；int main(){ int i，j，k，minn=INT _ MAXcinvntfor(I=1；I=n；一)中国b国c国；for(I=1；I=t；I) /**分组01背包，分组取*/{ for(j=v)；j=0；j-)f[I][j]=f[I-1][j]；/* *将第K组的值初始化为前一组。有可能这个组拿不到物品(值太低)*/for(k=1；k=n；K) /**循环N项*/if(c[k]==i) /**项属于组I */for(j=v；j=a[k]；J-)/* *用第I项测试是否能得到更大的值*/f [I] [J]=max (f [I] [J]，f[I-1][J-A[K]]B[K])；} coutf[t][v]；返回0；}同样，分组背包也可以使用一维数组。

　　#包含位/标准数据。使用命名空间标准；int n，m，dp[100005]，a[10005]，b[10005]，c[10005]；Int ()/* * P1757田童组背包，80分代码*/{ int i，j，k；cinmnfor(I=1；I=n；一)中国b国c国；for(k=1；k=n；K) /** k表示对于(j=m；j=0；J-)/* *对于每个dp[j]，我们用K组的所有物品来计算，因为是01背包。记住J必须从大到小*/for(I=1；I=n；I)if(c[I]==ka[I]=j)DP[j]=max(DP[j]，DP[j-a[I]]b[I])；cout DP[m]；返回0；}五、多个背包多个背包。项目的数量既不是一个也不是无限的。拿的时候只能选择0到k的物品。你可以把多个背包想象成分组背包，每个物品为一组，选择1，2.k个物品作为同一组的不同物品，这样多个背包和分组背包的编码非常相似。

　　多个背包在暴力枚举第I个物品的每一个可能数量时都有很高的复杂度，而且它还有一个极其巧妙的二元优化方法。比如第I个物品最多可以有20个物品，这20个物品可以分为1、2、4、8、5，这样我们就可以得到5个不同的物品，为他们做01背包。读者可以认为1、2、4、8对应二进制的后4位，可以匹配1之间的任意数.15，加上一个5，它可以匹配1.20.用01背包法计算时，最终的数量选择(最优值)一定会由二进制拆分数量组合而成。

　　#包含位/标准数据。使用命名空间标准；int n，m，a[1005]，DP[1005]；int()/* * p 1077 flowers */{ cinnm；int i，j，k；for(I=1；I=n；一)中国；DP[0]=1；for(I=1；I=n；I) /** i项*/{ for(j=m；j=0；J-) {/* *认为第I项取1，2.ai流域属于不同项目*/for(k=1；k=a[I]k=j；DP[j]=(DP[j]dp[j-k])00007；} } cout DP[m]；返回0；}六。背包值前面说过，背包问题一般是求最大值，也有一些求最大能装的容量或者方案数的问题。两类问题最大的区别就是求dp的代码。求值：dp[j]=max(dp[j]，DP[j-a[I]]b[I])；用空间换价值。求平均容量(设dp[0]=1)，只要标记是否能达到某个容量dp[j]=dp[j] dp[j-a[i]，如果能，dp[j]的值不为0。求方案数(设dp[0]=1)，当前方案累加前一个方案，DP[j]=(DP[j]DP[j-a[I])00007；现有的dp[j]方案数是由第一项增加的方案数累加而成，方案数的问题容易超出范围，一般要求有富余。保险起见，建议用龙龙型。

　　七。总结背包问题的学习需要大量的实践，才能掌握发现背包三要素的诀窍。P2066机器分配，比如我们可以把每个公司不同的使用时间看成是分组背包，因为这个组里每个公司只能选择一种机器使用时间。背包类型确定后，这个问题可以通过分组一维算法或者二维算法来解决，解决方案会更清晰。

　　这里有一个练习，让读者看看这是一个什么样的背包问题(答案在本文第二段用彩色标出)

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。