多背包问题的计算

本文讨论二个附加限制的多背包问题:限定总件数的多背包问题和0、1多背包问题,给出了它们的动态规划算法。限定总件数的多背包问题的算法所需的空间为O(BM),时间为O(nBM+kB~2),0、1多背包问题的算法所需的空间为O(min{2~(kn/2),nM~k}),时间为O(min{k·n~(kn/2),knM~k}),其中n为物品的种类数或件数,k为背包数,M=max{M_i:1≤i≤k},M_i(1≤i≤k)是第i个背包允许的最大重量,B是允许装入的最大总件数。