【摘 要】
：
背包问题是组合优化中的一个经典的NP-难题，其应用十分广泛，它不仅在投资决策问题、装载问题等方面有应用，而且常以子问题的方式出现在大规模的最优化问题中。本文在带指派限制
论文部分内容阅读
背包问题是组合优化中的一个经典的NP-难题，其应用十分广泛，它不仅在投资决策问题、装载问题等方面有应用，而且常以子问题的方式出现在大规模的最优化问题中。本文在带指派限制的多背包问题的基础上，增加了限制条件，从而得到了本文所要讨论的两个问题:
(1)给定n个物品U={u1，u2,...，un}，m个背包V={v1，v2,...，vm}，每个背包vi的容量为ci，每个物品uj放入背包vi时的大小为Wij，产生的价值为Pij。给定集合Aj={vi∈V|uj可以放入背包vi中}，集合Bi={uj∈U|uj可以放入背包vi中}，要求|Bi|≤2.问:如何将这些物品放入给定的背包中，使得每个背包所装物品的总大小都不超过背包的容量，且∑mi=1 p（vi）达到最大。此问题称为Max-Sum型带特殊指派限制的多背包问题。
(2)给定n个物品U={u1，u2，...，un}，m个背包V={v1，v2,...，vm}，每个背包vi的容量为ci，每个物品uj放入背包vi时的大小为Wij，产生的价值为Pij。给定集合Aj={vi∈V|uj可以放入背包vi中}，集合Bi={uj∈U|uj可以放入背包vi中}，要求1≤|Bi|≤2.问:如何将这些物品放入给定的背包中，使得每个背包所装物品的总大小都不超过背包的容量，且min1≤i≤mp(vi)达到最大。此问题称为Max-Min型带特殊指派限制的多背包问题。
上述两个问题中，j=1，2,...，n，i=1，2，...，m，每个背包的价值p（vi）为背包所装物品的价值之和。本文对问题(1)给出了一个复杂度为O((|U|+|V|)2·|U|)的多项式时间算法。对问题(2)给出了一个1/2-近似算法。
其他文献
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
Hilbert零点定理是交换代数中的一个经典结果,到目前已经有许多证明方法,可是这些证明大都不能显式的给出系数多项式的次数的一个上界,这称为“有效Hilbert零点”问题(具体叙
在工程、经济和生物等领域存在着大量的时变随机系统,对该类系统进行预测与控制得到了研究者和工程师的广泛关注。其中,估计与滤波是对该系统进行预测和控制的重要环节。本文
本文研究无限维系统的干扰解耦和几乎干扰解耦问题,包括控制算子有界和无界两种情形下的干扰解耦问题,以及单输入单输出系统的干扰解耦和几乎干扰解耦问题.主要采用有限维逼
本文通过几例化学实验创新实例的设计来阐述中学化学实验创新教学的尝试与体会。
In this paper, several innovative examples of chemical experiments are designed to i
基于当前我国高中数学教学现状,教师要想进一步提升教学质量,对学生实施科学的教育和指导,就应该积极探索和创新教学模式,增强数学教学的科学性和合理性,为学生数学学习创造
路由是在网络中选择运送物品的路径的过程,它在各种网络中都有应用。在本文中,我们主要讨论了无线通讯网络和交通运输网络中与路由相关的两个组合优化问题,即最少最短路中间
针对传统化学课堂活力不足、学生学习缺乏动力的现状,笔者提倡与强调自主学习。现就如何培养学生自主学习化学的意识,笔者提出几点看法。
In response to the lack of vital
三维重建作为计算机视觉中一个重要的研究任务，一直以来都是计算机视觉领域的研究热点。实现三维重建通常需要以下两个步骤:摄像机标定，摄像机运动参数恢复。因此许多学者对这
复发事件数据和纵向数据在纵向研究(比如医疗跟踪研究)中经常出现,它们是两类典型的复杂数据类型,对这两种数据的研究具有重要的理论意义和实际应用价值。在本文中,我们分别