研究了带背包约束的基数公平分配问题,即将给定的n个物品放入m个背包,在不超过背包容量的情况下,使得背包中装入的最小物品数尽可能大.通过预处理,可以假定每一个实例的最优值为k且n=km.得到如下的结果:①当所有背包的容量均相同时,通过对3-划分问题的归约证明了该问题不存在近似比大于2/3的近似算法,并基于贪婪法给出一个目标函数至少为k-1的近似算法;②当背包的容量不等时,通过对3维数值匹配问题的归约证明了该问题不存在近似比大于1/2的近似算法,并基于线性规划取整算法给出一个目标函数至少为k-2的近似算法.
背包问题 公平分配 近似算法 贪婪法 迭代取整