动态规划之背包
动态规划之背包
背包问题·容量有限·物品有价值·取物品遵循给定规则?求最大收益·状态定义·转移优化
背包问题 • 容量有限 • 物品有价值 • 取物品遵循给定规则 • 求最大收益 • 状态定义 • 转移优化
01背包·Eason挖开个矿洞单面有矿石，每个矿石有自已的体积cri和价值vrilEason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石·O（NM）：用fii表示考虑1~i个物品花费i代价最大收益，转移过程为f][i]=max(f[i-1]],f[i-1Ji-c[i]]+V[i]]for(intislit<an;t++)for (int j=o;j<=n;jt+)f[j]-std::nax(f[ti],f[tj-c[i]+v[i;ans=f[n][n];
01背包 • Eason挖开一个矿洞里面有矿石，每个矿石有自己的体积C[i]和价值V[i]， Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石 • O(NM)：用f[i][j]表示考虑1~i个物品花费j代价最大收益，转移过程为 f[i][j]=max{f[i-1][j],f[i-1][j-C[i]]+V[i]}
完全背包Eason挖开一个矿洞里面有矿石，每种矿石有自已的体积Cu和价值Vu，每种都有无限个。Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石·O（NM^2）：每个节点拆为若干个同样的物品再做O1背包·O（NMIgM）：每个节点拆为大小分别为原来2^i倍的物品在做01背包·O(NM）：对于fui，令i=kC]+b，改fori=OtoM为forb=1toC和fork=OtoM/CforCinti<n:i++for(int b=o:bec[u]:b++)f[ib]-f[ij[b]inttmp=b;[tmp] to f[t] ts the best strategy//tmpfrifor(intk=i;ksm/c[ij:k++)tntj=kclil +b:if(fit1[tmp] + (-tnp) / c[] *v[t] f[t-[])NPf[[tmp]+（tnp)/[]*[t];fEURans-f[n][m];
完全背包 • Eason挖开一个矿洞里面有矿石，每种矿石有自己的体积C[i]和价值V[i]，每种都有无限 个。Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石 • O(NM^2)：每个节点拆为若干个同样的物品再做01背包 • O(NMlgM)：每个节点拆为大小分别为原来2^i倍的物品在做01背包 • O(NM)：对于f[i][j]，令j=kC[i]+b，改for j = 0 to M为for b = 1 to C[i]和for k = 0 to M/C[i]
多重背包，Eason挖开一个矿洞里面有矿石，每种矿石有自已的体积CO和价值VU，每种有LU个Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石·O（NM)：利用具有单调性的队列对完全背包进行优化实现抛弃限制之外的状态以符合题意forCintn:++for (intb-o;b<std::nincil,m)ib++)tplpro//pt,pr :two potnter point at the begin or end of queue/quea sequence to store queue,thetrue queueisque[pl,pr)for(intko:k<m/c[ij:k++)(intj=kc[u]+b:while(plpr&&jque[pu]>l[i]c[i])D1++while (pipr&&f[t][que[pr-i]]+(-que[pr-a])/ c[t]-v[i]f[t1][])pr..ouelprf[tque[p]]+que[p]/c[]v[];frillilans=f[n][m]
多重背包 • Eason挖开一个矿洞里面有矿石，每种矿石有自己的体积C[i]和价值V[i]，每种有L[i]个。 Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石 • O(NM)：利用具有单调性的队列对完全背包进行优化实现抛弃限制之外的状态以符合 题意