共查询到19条相似文献,搜索用时 734 毫秒
1.
连续背包问题贪婪算法最优解的实现 总被引:1,自引:0,他引:1
贪婪法是用于设计数值最优化问题的算法之一,它能应用于求解不同领域的多种问题,如应用于集装箱问题的背包贪婪算法。贪婪法不追求最优解,不要回溯,只希望得到较为满意的解,使用贪婪法不能保证一定得到最优解。本文通过对连续背包问题不同贪婪准则的讨论,给出了一个贪婪算法最优解实现的C程序。 相似文献
2.
冯光毅 《计算机光盘软件与应用》2013,(24):99-100
贪婪算法作为一种求最优解问题的方法,具有简便、迅捷的特点,然而贪婪算法因其基于局部求最优解的特点,决定了其在很大程度上无法得到问题的最优解。本文通过对[0-1背包问题]以及部件加工问题的分析,阐述了贪婪算法的应用以及贪婪算法存在的局限性,进而引出贪婪算法的优化方案——k阶优化方法,进一步对求最优解问题进行完善和归纳。 相似文献
3.
整数背包问题的应用及其算法研究 总被引:7,自引:0,他引:7
本文应用整数背包问题有关理论,对CD曲目智能编辑转录和条型钢材优化切割等应用问题进行了讨论,提出了一个解决此类问题的数学模型,之后,分别给出了求其最优解和近似解的算法,并提供了该数学模型及算法的应用建议。 相似文献
4.
5.
针对背包问题传统的解决方法有动态规划法、分支界限法、回溯法.传统的方法不能有效地解决背包问题.文中提出二重结构编码的遗传算法解决背包问题,是一种适合于在大量的可行解中搜索最优解的有效算法,在约束条件的处理上结合贪婪算法,既加快了算法的收敛速度,又克服了传统方法容易陷入局部最优的特点,提高了搜索效率.通过计算机仿真试验结果表明,二重结构编码的遗传算法比基本遗传编码有更好的近似解,充分证明了使用二重结构编码的混合遗传算法来求解背包问题的有效性和实用性. 相似文献
6.
7.
收缩背包问题的并行分枝界限算法 总被引:1,自引:0,他引:1
收缩背包问题(collapsing knapsack problem,CKP)是0-1背包问题的变体,其中背包的容量为所装物品数量的非增函数,针对并行计算的需求,在对CKP问题分解的基础上,给出了求解每个子问题的权分枝界限算法,提出了基于MIMD-DM的收缩背包问题的并行分枝界限算法;并在曙光1000上设计和实现了该算法,以消息传递方式来解决子算法最优解的播送问题,同时给出了子问题的求解顺序,讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响。 相似文献
8.
求解0-1背包问题的混沌遗传算法 总被引:1,自引:0,他引:1
提出一种改进的混沌遗传算法来求解0-1背包问题。通过利用幂函数载波技术增强混沌搜索的遍历性,把混沌搜索得到的最优解直接作为新群体嵌入遗传算法来改善遗传算法的早熟问题,从而使算法有能力避免陷入局部极值而快速收敛于全局最优解。仿真实验结果表明了该算法求解0-1背包问题的有效性和适用性。 相似文献
9.
讨论一类大规模系统的优化问题,提出一种递阶优化方法.该方法首先将原问题转化为多目标优化问题,证明了原问题的最优解在多目标优化问题的非劣解集中,给出了从多目标优化问题的解集中挑出原问题最优解的算法,建立了算法的理论基础.仿真结果验证了算法的有效性. 相似文献
10.
11.
A. Drexl 《Computing》1988,40(1):1-8
The multiconstraint 0–1 knapsack problem encounters when deciding how to use a knapsack with multiple resource constraints. The problem is known to be NP-hard, thus a “good” algorithm for its optimal solution is very unlikely to exist. We show how the concept of simulated annealing may be used for solving this problem approximately. 57 data sets from literature demonstrate, that the algorithm converges very rapidly towards the optimum solution. 相似文献
12.
In this paper, we study the sensitivity of the optimum of a max–min combinatorial optimization problem, namely the knapsack sharing problem, to the perturbation of the profit of an arbitrary item. We mainly establish the interval limits of each perturbed item by applying a reduction of the original problem into a series of single knapsack problems. We propose a solution procedure in order to establish these interval limits. The principle of the method is to stabilize the optimal solution in the perturbed problem, following two cases: (i) when the item belongs to an optimal class and (ii) when the item belongs to a non‐optimal class. We also consider either the problem admits a unique or multiple optimal classes. Finally, we evaluate the effectiveness of the proposed method on several problem instances in the literature. 相似文献
13.
This paper introduces a fast heuristic based algorithm for the max-min multi-scenario knapsack problem. The problem is a variation of the standard 0-1 knapsack problem, in which the profits of the items vary under different scenarios, though the capacity of the knapsack is fixed. The objective of the problem is to find the optimal packing of a set of items so that the minimum total profits of the items in the knapsack over all different scenarios is maximized. For some large-scaled instances, traditional branch-and-bound techniques cannot find an optimal solution within reasonable time, thus we propose a collection of incomplete m-exchange algorithms which are able to produce high quality solutions in just a few minutes of cpu time. Various computational results are also given. 相似文献
14.
Dynamic Programming Revisited: Improving Knapsack Algorithms 总被引:1,自引:1,他引:0
U. Pferschy 《Computing》1999,63(4):419-430
The contribution of this paper is twofold: At first an improved dynamic programming algorithm for the bounded knapsack problem
is given. It decreases the running time for an instance with n items and capacity c from to , which is the same pseudopolynomial complexity as usually given for the 0--1 knapsack problem. In the second part a general
approach based on dynamic programming is presented to reduce the storage requirements for combinatorial optimization problems
where it is computationally more expensive to compute the explicit solution structure than the optimal solution value. Among
other applications of this scheme it is shown that the 0--1 knapsack problem as well as the bounded knapsack problem can be
solved in time and space.
Received: October 15, 1998; revised March 10, 1999 相似文献
15.
A. A. Korbut I. Kh. Sigal 《Journal of Computer and Systems Sciences International》2010,49(5):757-764
Ratios δ of the values of objective functions of optimal Boolean (or integer) to the values of greedy solutions for the knapsack
problem are considered. The relationship of the parameter δ with the ratio Δ of the values of objective functions for the
optimal solution of linear relaxation to the values of optimal integer solution was found. Two-sided estimates for δ and Δ
were obtained. A computational experiment was conducted to investigate the ratio of δ of problems of one- and two-dimensional
knapsack problems with Boolean variables. A hypothesis on asymptotic behavior of the ratio δ with growth of the number of
problem variables was formulated. 相似文献
16.
V. A. Mikhailyuk 《Cybernetics and Systems Analysis》2011,47(6):871-880
It is shown that an algorithm polynomial on average with respect to μ and that determines an optimal solution to a set cover problem that differs from the initial problem in one position of the
constraint matrix does not exist if the optimal solution of the original problem is known and DistNP is not a subset of Average-P.
A similar result takes place for the knapsack problem. 相似文献
17.
本文介绍了属于NP难问题的无界背包问题的一种新的精确算法,基于问题的几何结构通过二分搜索方法不断减小解空间,最终直接求出问题的最优效益值和最佳装包方案。当待装入包中的物品数量固定时,算法的时间复杂性为线性时间,初步解决了求解当前呈指数增长背包实例时存在的困难,实验中各种数据实例证明与常用的MTU2和EDU相比,该新算法在理论上是可行的。 相似文献
18.
19.
In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy. 相似文献