背包问题九讲和源程序(答案).doc

01 USACO USACO Training P01: 01NViciwifivivfiv=maxfi-1v,fi-1v-ci+wiivii-1ii-1vfi-1vii-1v-cifi-1v-ciiwiO(N*V)O(V)i=1.Nfi0.Vf0.Vifvfivfivfi-1vfi-1v-cifivifvfi-1vfi-1v-civ=V.0fvfvfv-cifi-1v-cifor i=1.N for v=V.0 fv=maxfv,fv-ci+wi;fv=maxfv,fv-cifiv=maxfi-1v,fi-1v-cifv-cifi-1v-civfivfiv-ciP02010101ZeroOnePack01costweightprocedure ZeroOnePack(cost,weight) for v=V.cost fv=maxfv,fv-cost+weightv=V.0costf0.cost-101for i=1.N ZeroOnePack(ci,wi);f00f1.V-fNf0.V0f00nothing-000101 P02: NViciwi0101201fivivfiv=maxfi-1v-k*ci+k*wi|0=k*ci=v01O(N*V)fivO(v/ci)O(VN)0101ijci=wjjjiO(N2)VO(V+N)010101iV/ciiV/ci0101ici*2kwi*2kkci*2k=Vi2kO(log(V/ci)O(VN)O(VN)for i=1.N for v=0.V fv=maxfv,fv-cost+weightP01vP01v=V.0ifivfi-1v-ciiifi-1v-ciiifiv-civ=0.Vfiv=maxfi-1v,fiv-ci+wiprocedure CompletePack(cost,weight) for v=cost.V fv=maxfv,fv-ci+wiO(VN) P03: NViniciwiini+101nifivivfiv=maxfi-1v-k*ci+k*wi|0=k0ni131,2,4,6ninii0.ni0.2k-12k.niiO(log ni)O(V*log ni)01O(log amount)amountprocedure MultiplePack(cost,weight,amount) if cost*amount=V CompletePack(cost,weight) return integer k=1 while knum ZeroOnePack(k*cost,k*weight) amount=amount-k k=k*2 ZeroOnePack(amount*cost,amount*weight)O(VN)O(VN)O(1)DPNOIPO(V*ni)O(V*log ni)NOIPO(VN) P04: P01P02P030101P01P02O(VN)for i=1.N if i01 for v=V.0 fv=maxfv,fv-ci+wi; else if i for v=0.V fv=maxfv,fv-ci+wi;O(VN)NOIPP03O(log ni)01for i=1.N if i01 ZeroOnePack(ci,wi) else if i CompletePack(ci,wi) else if i MultiplePack(ci,wi,ni)01 P05: 12iaibiVUwifivuivufivu=maxfi-1vu,fi-1v-aiu-bi+wivuM1Mfvmvm01f0.V0.M P06: NViciwifkvkvfkv=maxfk-1v,fk-1v-ci+wi|ikfor k for v=V.0 for ik fv=maxfv,fv-ci+wibetafor v=V.0for ikP02P07 P07: ijijNOIP2006n2n+1P06P06 P02 i010.V-cif0.V-ciV-ci+1ci+kfk+wi01iV-ci+1P0601DPDPP08NOIP2006 P08: V0.Vhvh(v)h0.VvhVcw01h(c)=w0vch(v)=v/c*w0nh(v)=v/c*wvcv/c=n0h0.Vvvh(v)=0h(v)vP07hlv0.Vvvhlf(v)f(v)=maxh(k)