目录
完全背包
优化1 )输入优化2 )二进制优化3 )重复放入的01背包多重背包总结完整背包有大小为m的背包，有n种物体，每个物体的价值为Vi，大小为Ai，并且每个物体有无限个。 背包能容纳的最大价值是多少？
(Lintcode - 440 )
这就是完全背包问题。 完全背包是指物品的数量都是无限个。
很明显可以转换成01背包。 每个物体都是无限个的，但不能超过背包的容量。 假设第一个物体的大小为A1，则可以假装大小分别有多达A1、2 A1、3a 1…(m/a1 ) a1 )的一系列物体。 然后把kA1分别放进背包里。 这样的时间复杂度与o(VN*sum ) k ) )非常大。 其状态转移方程式如下
dp[i 1][j]=max(dp[i][j]，dp[i][j - k * A[i]] k * V[i]
for(intI=0； i A.size (； I ) for(intj=m； j=0； -j ) for(intk=0； k * A[i]=m； k ) if(j-k*a(I )=0) f(j )=max ) f(j )、if(j-k*a(I ) ) k * v (I ) )； 优化一)如果输入优化的项目列表很多，可以首先改进项目列表。 对于物品j、k，如果Aj=Ak且Vj Vk，则j相对于k昂贵且没有价值，肯定会被舍弃。
此外，项目列表中可能有大小大于m的项目，必须将其排除。
优化2 :如果二进制最多只能容纳19个Ai，实际上只需要分别将1、2、4、8、4个Ai放入包中即可。 物体都可以分解成二进制数的个数放入包中，实际上也可以分解成其他进制数。 最终组合的数量也是19个，和包里装了19个Ai一样。 时间的复杂性是o(VN*sum ) log (k ) )。
for(intI=0； i A.size (； I ) { int j=1； while(j*a[I]m ) for ) intk=m； k=j * A[i]； -k(f ) k )=max(f(k )，f(k-j*a(I ) ) j*v ) I ) j； j=j 1； (优化3 )有些同学可能还记得反复放的01背包，我们在写01背包的时候做错了。 从前到后遍历背包的容量，同一物体被反复放入。
这正是我们在完整的背包里想要的东西，东西数量无限，当然可以一直放在背包里。
时间复杂度为o(VN )。
for(intI=0； i A.size (； I ) for(intj=a[I]； j=m； j ) f(j )=max ) f(j )，f(j-a ) (I ) )； 多重背包有大小为m的背包，有n种物体。 每个物体的价值是Vi，大小是Ai。 这个物体共有Ci个。 背包能容纳的最大价值是多少？ (lint代码- 798 )
很容易想到按物体分开放的方法，把这个问题作为01背包放进去，每个物体放Ci次。 时间复杂度为o(VNC )。
for(intI=0； i prices.size (； I ) for(intk=1； k=amounts[i]； k ) for(intj=n； j=prices[i]； -j ) DP[j]=max (DP [ j-prices [ I ] weight [ I ]，DP [ j ]； 该方法也可以采用二进制优化来降低时间复杂度到o(VNlog(c ) )。
虽然也有用单音队列优化多路背包的方法，但是我现在只学习单音队列，还不知道如何优化多路背包问题。 稍后知道了的话就补上。
总结目前已经知道如何解决基础背包问题，而且背包问题一般要求几种方法来满足背包，或者混合三种背包。 这样简单的变化，可以用至今为止所述的方法来解决。
返回目录