-1-
中国科技论文在线
一类 0-1背包问题的贪婪遗传算法
金怀群
韩山师范学院数学与信息技术系，广东潮州 (521041)
摘 要：针对一类 0-1背包问题提出一种新的混合遗传算法，贪婪遗传算法使用贪婪法则产
生第一个染色体，并在进化过程中利用贪婪算子改进部分可行解。在使用高变异概率的同时
使用低交叉概率，充分发挥变异操作在遗传算法中重要而基本的作用，克服遗传算法的局限
性。通过对大约 400,000个精心构造的新实例的计算发现，找到最优解的平均时间随系数增
大而变得小于一些著名的完全算法，平均在 与 之间，而平均代数为 1到 40。
关键词：背包问题；贪婪算法；遗传算法；贪婪遗传算法
中图分类号：
1．引言
最近的研究表明，背包问题（Knapsack Problems，简称 KP）仍然难于解决[1]。虽然，
背包问题普通人理解起来也毫不费力，而且过去几十年，有关 KP 的完全算法（Exact
algorithms）、近似算法（Approximate algorithms）与启发式方法（Heuristics）都发表了大量
研究成果。但是，由于以前的计算测试限于少数有高度结构的实例（highly structured
instances），不能显示 KP的全部特征。D. Pisinger从两方面着手构造 0-1背包问题（0-1 or
Binary Knapsack Problem, 简称 0-1KP）的新实例。其中之一，是用更大的系数测试原先的
标准实例，并利用基于分支限界（branch and bound）与动态规划（dynamic programming）
的完全算法进行许多计算实验。这些算法经过几十年的改进，达到最新技术水平，几乎可以
解决文献上所有传统的标准实例。但对于精心构造的新实例，执行情况很差。
或许 KP是“比较容易”的 NP-难（NP-hard）问题之一，应用遗传算法（Genetic Algorithm,
简称 GA）解决 KP远远少于用 GA解决旅行商问题（Traveling Salesman Problem，简称 TSP），
虽然它们都是典型的组合问题，而且在理论和实际上都有很重要的价值。就参考文献[2, 3, 4]
来说，用 GA解决 KP主要讨论了约束条件下的编码方法，有二进制编码法、顺序表达法、
变长表达法和二重结构编码法等，以及相应的遗传算子的设计；对于迭代过程产生的不可行
解，通常采用惩罚法或者解码法来解决；后者利用贪婪法则在解码的过程中把不可行解转化
为可行解，从而进一步构成某种混合遗传算法（Hybrid Genetic Algorithm, 简称 HGA）。P. C.
Chu和 J. E. Beasley[5]综述 KP研究文献之后，提出一种解决多维背包问题（Multidimensional
Knapsack Problem, 简称MKP）的遗传算法，计算结果显示，对于各类大规模的更难求解的
MKP，只需适度的计算努力，GA就能够获得高质量的解，而且优于其它一些启发式方法。
其中，结合问题的具体知识构造的修补算子(repair operator)确保每一个子代个体都是可行
解，以应付MKP的约束条件与可行性。近年来，A. Simões等人[6]利用生物学的 Transposition
机制，提出一种代替传统交叉的遗传算子——转置，在求解 0-1KP 和函数优化领域，转置
总是优于交叉；Steven O. Kimbrough等人[7]则探索双种群遗传算法在约束优化中的应用，对
KP的求解获得较好的结果。
1994年，V. Gordon等人[8]利用分支限界法和深度优先法（depth-first methods）这样简
单通用的搜索算法和 GA求解同样的 0-1KP。结果发现，对于小的问题，前两者比 GA更快
产生解；对于大的问题，前两者在寻找最优解和寻找近似解都比 GA出色，尽管他们的 GA
利用了有用的局部信息。根据获得的数据，他们认为需要更多了解哪些问题适合于 GA而哪
-2-
中国科技论文在线
些不，像 0-1KP 也许不太适合于盲目遗传搜索，可能需要改用混合方法。无疑地，我们需
要更好地了解哪些问题实际上不能由完全算法解决，而是适用于遗传方法或混合方法，或者
相反。另外，文献[8]还提到 Martello和 Toth使用更专门的分支限界法，在 1分钟之内解决
更大的 KP。这正是文献[1]涉及的前人工作之一。
本文提出一种新的混合遗传算法——贪婪遗传算法（Greedy Genetic Algorithm, 简称
GGA），用于解决一类 0-1KP。1995年，曾有人应用 GA专门解决这一类 0-1KP[9]，文中给
出专门设计的评估函数，值得借鉴。其初始群体随机产生，群体规模 40，最大代数 250，标
准交叉运算、但 pc 不明，变异包括三个过程：随机位变异、邻居交换、随机两点间二进制
位反转，三者的概率分别是 、和 。结果发现，GA能够容易而且迅速地找
到接近于最优值的解，然而，从接近于最优值的解到达最优解很慢，因此加入一个局部搜索
程序改善求解速度。
下一节介绍 0-1KP；第 3节给出并论述 GGA；第 4节说明计算实验的情况并分析计算
结果；最后得出结论。
2．0-1背包问题
定义
0-1KP的传统定义是，一个有 n个项目的集合和一个有限容量 c的背包，每个项目有重
量 wj连带价值 pj，c、wj和 pj为正整数（j = 1, …, n）。问题要求挑选具有总价值最大的项目
子集，其重量之和不超过背包容量。0-1KP可用如下整数规划描述：
其中各二进制决策变量 xj等于 1当且仅当项目 j被选中。一般说来，背包不能容纳所有的项
目，因为所选项目的总重量不能超过背包容量。结果，不失一般性，假设所有项目的重量之
和大于 c，而每个项目的重量小于 c。即：
Subset-Sum Problem
当 pj = wj（j = 1, …, n）时，0-1KP称为 Subset-Sum Problem（SSP）[10]，这个问题是寻
找一子集，其重量之和小于等于 c。可以证明，SSP是 NP-难问题。实际应用中经常出现这
一类特殊情况，即应该达到一定的数量指标，其负偏差必须最小，且不许正偏差。
由于 pj = wj，于是获得一个装满的背包就是唯一的目标。但 SSP实例仍象其它 0-1KP
实例一样难以解决[1]，因为大多数深思熟虑的上界返回同一平凡值 c，从而在找到最优解之
前，不能使用约束规则切断分支。而在项目数不太少的问题中，求解 0-1KP 的分支限界法
对于 SSP甚至会退化成完全枚举。
解决 0-1KP的方法显然可以用来解决 SSP。然而，SSP值得特殊处理是因为专用算法通
( )
( )
{ } ( )3 .,,1 ,1,0
2 , .
1 max
1
1
njx
cxw
xp
j
n
j
jj
n
j
jj
…=∈
≤∑
∑
=
=
( )
( )5 ,...,1 ,
4
1
njcw
cw
j
n
j
j
=≤
>∑
=
-3-
中国科技论文在线
常给出更好的结果。反之，也有人把求解 SSP的多项式时间近似方案推广到 0-1KP[10, 11]。
3．贪婪遗传算法
这里，我们给出贪婪遗传算法（图 1）：
begin
t Å 0;
初始化 P(t);
评估 P(t);
while 不满足终止条件 do
begin
重组 P(t)获得 C(t);
利用贪婪算法操作 C(t);
评估 C(t);
采用 elitist model从 P(t)选择最佳染色体进入 C(t)形成 P(t+1);
t Å t + 1;
end
end
图 1 贪婪遗传算法（GGA）
其中，P(t)为父代种群，C(t)为子代种群。种群中每个染色体都是 KP的一个可行解。
贪婪算法
除了完全算法，求解 SSP的最直接途径是贪婪算法（Greedy Algorithm）。贪婪算法简单
得出奇，在每一步“贪婪地”选择最好的部分解，毫不顾及眼前局部的选择对今后全局的影响，
因此，一般不能得到最优解，只能获得近似解。对于 SSP，可按任何顺序逐项检查，将合适
的新项目装入背包，直至不能再装为止。如果事先对所有项目按其重量降序排列，效果更好。
许多文献都利用贪婪算法求解 KP，包括前述的 HGA[4]。由于遗传算法与贪婪算法的互
补性，混合算法通常比单一算法优越。但是，我们应用贪婪算法有所不同，一是在产生初始
群体时，二是在遗传迭代过程中对可行解与不可行解的进一步处理，如下所述。
初始群体
贪婪算法采用的二进制决策变量自然就是遗传算法采用的二进制编码，与 HGA一般遵
守的第一个原则相符[12]，即保留包含在原编码中的有关知识。贪婪算法因此可产生 GGA的
第一个染色体 s0，s0是一个近似解。这样，按照 HGA一般遵守的第二个原则，GGA得到的
解至少不会比贪婪算法的解差。初始群体其余个体由 2-opt邻域映射获得。当然，我们只随
机选择 s0的邻域中的部分可行解。
贪婪算子
进一步，不妨把应用贪婪法则的过程称为贪婪算子（图 2），相当于修补算子的 ADD阶
段[5]。我们的贪婪算子由贪婪概率 pg 控制操作，就像交叉算子和变异算子分别由交叉概率
pc和变异概率 pm控制操作一样。当 GA 作全局最优搜索时，贪婪算子对未装满的背包再次
操作，直至不能再装为止，即对代表近似解的染色体进一步改进[11]。
begin
背包剩余容量 r = 背包容量 c - 染色体 i的已装重量Wi
-4-
中国科技论文在线
for j=1 to n
如果项目 xj = 0，并且 wj <= r
则 xj = 1;
r = r - wj;
end
图 2 贪婪算子
这样，在 GA典型的重组选择迭代中嵌入贪婪算子，即直接由贪婪算子替代常用的局部
爬山法，对部分新产生的后代在其进入种群之前应用贪婪算子操作，使之移动到最近的局部
最优点，甚至全局最优点。因此，GGA具有典型的 HGA形式[2]。
这也是混合策略一般遵守的第二个原则的另一途径[12]，吸收原有算法的优点，把原有
算法中的一系列变换结合到 HGA中可能很有用。例如，退火演化算法就是把模拟退火算法
（Simulated Annealing）中的退火过程与群体的演化结合而成的。
约束优化
0-1KP作为一个单约束的整数规划，应用 GA求解时也必须满足约束。对染色体作遗传
操作产生的不可行后代，多数采用惩罚法或者解码法来解决，参考文献[5]则有修补算子的
DROP 阶段。GGA 采用拒绝策略，严格限制进入种群的新生染色体，凡不可行的，一律抛
弃。对于可行解，GGA利用贪婪算子按贪婪概率部分改进。而更多更复杂的约束优化处理，
可参考有关文献，其中各种满足约束的策略有待进一步的研究[2]。
遗传算子
GGA 在父代种群 P(t)中随机选择两个染色体，进行一点交叉和位点变异操作，生成新
的染色体，经译码，把可行解作为子代种群 C(t)中的染色体。这里，交叉概率 pc为 ，变
异概率 pm为 。
变异概率 pm如此之大，随机性加强，如何保证算法收敛？我们知道，GA 的运行依赖
各种各样的参数。但是，迄今为止，这些参数的设置还没有成熟的原则和方法，基本上依赖
经验和对所求解问题的了解，因此需要认真选取。而如何有效配合使用交叉和变异这两种操
作，仍然值得研究。
前人早已指出[3]，GA存在未成熟收敛即早熟缺陷，这主要是 pm太低，以至于不能使搜
索转向解空间的其他区域进行搜索。pm 取较大值可维持种群多样性，防止早熟。另外，交
叉操作使种群中的染色体具有局部相似性，从而使搜索停滞不前即爬山能力差。
徐宗本等人在 1990年代后期完成的工作揭示了一个重要事实[13]：交叉操作的作用是有
限的，变异操作的作用更为重要而基本。这与传统对 GA的认识有很大的区别，交叉的作用
是在“子空间”上搜索，而变异的作用是不断改变子空间，从而扩大搜索范围，原则上可以扩
大到整个空间。或者说，变异算子有能力从任何个体出发搜索到整个空间中的任何其他一个
个体，即整个空间是变异算子的搜索可达域。因此，如果说交叉算子是局部搜索算子，则变
异算子可认为是全局搜索算子。他们的研究表明：较大的 Pm使 GA在整个搜索空间中大步
跳跃，而小的 Pm使 GA聚焦于特别区域作局部搜索。一般在不使用交叉算子的情形，Pm取
较大值( ~ 1)；在与交叉算子联合使用的情况下，Pm通常取较小值( ~ )。当变异
算子用作核心搜索算子时，比较理想的是自适应设置 Pm，以实现 GA 从“整体搜索”慢慢过
渡到“局部搜索”。
-5-
中国科技论文在线
4．计算实验
提出解决某个问题的算法之后，除了理论分析，人们往往也通过计算测试，验证算法的
有效性。当然，具体如何评价 GA的性能是复杂又困难的，而且用于评价 GA的测试问题会
影响 GA的执行结果。由于现实存在的 KP数据很少在文献上报道，而且实际数据往往是偏
颇的，会在某个有限范围内变化，以此不能正确评价算法的性能，算法的适应性也缺乏保证。
因此，我们采用大规模计算来分析评价算法[14]。具体应用综合测试问题产生器 1生成大批随
机数据，这些测试数据蕴含的一些结构也许不存在于现实生活的实例中。
由于没有实现文献[9]描述的算法提纲的源代码，目前也未见应用 GA 求解这类 SSP 的
其他报道，因此，我们的计算测试将用于比较 GGA与文献[1]中各算法对于解决 SSP的性能。
许多文献都通过与其他完善的技术相比，评估新算法的价值，并说明新方法的可能性[5]。但
或许有人认为，比较遗传算法与完全算法的实验数据，以说明 GA性能是不合理的，特别是
运行时间。因为性能上，前者优于后者。其实未必[8]，而且应该注意的是，两者都各有新的
进展。
本节先给出一个实例的计算结果，进行初步对比；接着叙述综合基准测试（Synthetic
benchmark test）设计，然后给出计算结果并加以分析。
一个实例
文献[9]的实例项目数 n为 100 ~ 17,000，但具体数据不详。文献[3]的 KP实例 2倒是一
个 SSP。其 GA 是，惩罚系数 ，一点交叉、pc=，位点变异、pm=，初始群体
随机产生，群体规模 100，采用正比于适应度的比例选择机制。在 386PC上执行时间为 123s，
第 14代得到最优解。
而应用 GGA求解同一实例，1代就得到最优解，时间不到 。
综合基准测试
考虑算法 GGA对于不同的问题大小与数据范围的工作情况。在全部 397,272实例中，
问题大小即项目数 n分别为 50、100、200、500、1000、2000、5000和 10000，重量都均匀
分布在一个给定的区间[1, R]，其数据范围 R 分别为 1000、10000、100000、1000000 和
10000000。即共有 8×5＝40个类型，对于每个 n和 R，随机产生 100个实例，每个实例编为
H＝100个背包，每个背包容量如下：
其中测试实例编号 h = 1, …, H。在部分实例中，由于一些项目的重量不小于 ch，违背假设(5)，
对此，GGA不予计算，故全部实例不足 40万个，请参见表 1。
表 1 测试实例分布
R
n 103 104 105 106 107
50 9649 9654 9661 9648 9660
100 9851 9849 9854 9852 9856
200 9943 9954 9946 9946 9949
500 10000 10000 10000 10000 10000
1000 10000 10000 10000 10000 10000
2000 10000 10000 10000 10000 10000
5000 10000 10000 10000 10000 10000
( )6
1 1
∑
=+=
n
j
jw
H
hc
-6-
中国科技论文在线
10000 10000 10000 10000 10000 10000
GGA群体规模 100，采用最佳个体保存方法从 P(t)选择最佳染色体替换 C(t)中最差染色
体，从而形成 P(t+1)。GGA对每个实例执行 100轮、每轮 100代的遗传计算。对于所有 n，
贪婪概率 pg按照 R的大小设置如表 2：
表 2 贪婪概率 pg
R 103 104 105 106 107
pg
算法 GGA用标准 C实现，编译器为 gcc version 。运行的硬件环境是 Intel Celeron
CPU 。操作系统是 Fedora Core 2 Release, 内核版本 。
计算结果
计算结果如表 3~表 6所示。
表 3 找不到解的测试实例分布
R
n 103 104 105 106 107
50 39 121 292 645 4092
100 11 83 1272
200 176
500 3
1000
2000
5000
10000
由
表 3可知，有 %的测试实例在 100轮、每轮 100代的遗传搜索后没有找到最优解。
大多分布在 n=50、100，其中 R=107是最难解的。由于 GGA在遗传搜索过程中以装满背包
为终止条件，所以这 6,734个实例中部分是重量和小于背包容量 c的。
表 4 每轮均得最优解的测试实例分布
R
n 103 104 105 106 107
50 9580 7333 79 6 1
100 9850 9588 357 8 1
200 9943 9933 2113 4 2
500 10000 10000 8934 27 1
1000 10000 10000 9943 563 2
2000 10000 10000 9999 5066 9
5000 10000 10000 10000 9788 35
10000 10000 10000 10000 9992 1089
由表 4可知，每轮均得最优解的实例共 234,246个，占 %。结合表 3，其分布也很
好理解。
表 5 找到最优解的平均代数
R
n
103 104 105 106 107
50
100
200
-7-
中国科技论文在线
500
1000
2000
5000
10000
由表 5可得，找到最优解的平均代数最少 1代，最多 40代。事实上，即使最难解的实
例，也存在只需 1代就找到最优解的轮次。对于每一个 n，找到最优解的平均代数随 R的增
加而增加；对于每一个 R，找到最优解的平均代数基本上随 n的增加而减少，这与表 4每轮
均得最优解的实例分布相符。
表 6 找到最优解的平均运行时间（单位 ms）
R
n
103 104 105 106 107
50
100
200
500
1000
2000
5000
10000
由表 6 可知，找到最优解的平均时间最短 ，最长 。对于每一个 n，找到
最优解的平均时间随 R 的增加而增加；对于每一个 R，找到最优解的平均时间基本上随 n
的增加而增加。这与表 5的结果完成一致。
平均计算时间比较
文献[1]采用综合基准测试，对于中等大小的系数（R=1000, 10000），有 5个算法进行计
算；对于大系数（R=105, 106, 107），有 3个算法计算。全部测试运行在 Intel Pentium III, 933MHz
的机器上，指定 1 小时的时间限制给每类实例的全部 H 个实例。任何在时间限制之内没有
解决的实例，表中用破折号表示。其中，MT2 和 Expknap 都是分支限界算法，MThard 是
MT2 的一个特殊形式；Minknap 是一个动态规划算法，Combo 是以动态规划结合其它技术
的混合算法。
表 7 平均运算时间比较（R=103，单位 ms）2
n GGA MT2 MThard Expknap Minknap Combo
50
100
200
500
1000
2000
5000
10000
由表 7可知，GGA不如其它完全算法。
-8-
中国科技论文在线
表 8 平均运算时间比较（R=104，单位 ms）
n GGA MT2 MThard Expknap Minknap Combo
50
100
200
500
1000
2000
5000
10000
由表 8可知，结果比表 7有改善，优于其它完全算法的包括：n=200，GGA与 MT2；
n=200, 10000，GGA与MThard；n=50, 100, 200, 500, 1000, 2000，GGA与Minknap；n=50, 100,
200, 500, 1000，GGA与 Combo。
表 9 平均运算时间比较（R=105，单位 ms）
n GGA Expknap Minknap Combo
50
100
200
500
1000
2000
5000
10000
由表 9可知，结果进一步改善，GGA与完全算法平分秋色。对于每一个 n，GGA的结
果优于Minknap，但比 Expknap差。n=50, 100, 200, 500，GGA优于 Combo。
表 10 平均运算时间比较（R=106，单位 ms）
n GGA Expknap Minknap Combo
50 -
100 -
200 -
500 -
1000 -
2000 -
5000
10000 -
由表 10可知，对于每一个 n，GGA的结果优于Minknap；n=50, 100, 200，GGA优于
Expknap。n=50, 100, 200, 500, 1000，GGA优于 Combo。
表 11 平均运算时间比较（R=107，单位 ms）
n GGA Expknap Minknap Combo
50 - -
100 - -
200 - -
500
1000 - -
2000 - -
5000
10000 -
由表 11可知，对于每一个 n，GGA的结果优于Minknap；n＜5000时，GGA优于 Expknap；
除了 n=500, 5000, 10000之外，GGA均优于 Combo。这时，GGA优于完全算法。
-9-
中国科技论文在线
5．结论
本文提出了一种简洁有力地解决 SSP的新型贪婪遗传算法。大量的计算实验表明，GGA
高效、快速、稳健且寻优能力强。这主要得益于：⑴ 善用贪婪法则，用于产生初始群体并
在进化过程中改进部分可行解；⑵ 同时使用高变异概率与低交叉概率。众所周知，遗传算
法的局限性，例如早熟，共同的原因是变异概率太低，以至于不能使搜索转向解空间的其他
区域进行搜索。另一个是爬山能力差，因为交叉算子使种群中的染色体具有局部相似性，从
而使搜索停滞不前。进一步，GGA找到最优解的平均时间随 R的增大而变得小于MT2等完
全算法，这种优势突破文献[8]的结论。
GGA在 SSP上取得良好效果，说明该算法很有潜力，可尝试用来解决 0-1KP。但是，
GGA 只是针对一类 0-1KP，而且从文献[1]的结果可知，SSP 并非最难解决。因此，要全面
解决 0-1KP，需要进一步对 GGA加以改进。
参考文献
[1] Pisinger David. Where are the hard knapsack problems? [J] Computers and Operations Research, 2005, 32(9):
2271~2284
[2] 玄光男，程润伟. 遗传算法与工程设计[M]. 北京：科学出版社，2000
[3] 陈国良，王煦法，庄镇泉，王东生. 遗传算法及其应用[M]. 北京：人民邮电出版社，1996
[4] 王小平，曹立明. 遗传算法——理论、应用与软件实现[M]. 西安：西安交通大学出版社，2002
[5] Chu P C, Beasley J E. A Genetic Algorithm for the Multidimensional Knapsack Problem[J]. Journal of Heuristics,
1998, 4: 63~86
[6] Simões Anabela, Costa Ernesto. An evolutionary approach to the zero/one knapsack problem: testing ideas from
biology[C]. In: Proceedings of the Fifth International Conference on Artificial Neural Networks and Genetic
Algorithms (ICANNGA ‘2001), Prague, Czech Republic, 2001, 22~25
[7] Kimbrough S. O., Lu M., Wood D. H., and Wu D. J. . Exploring a two-market genetic algorithm[C]. In: W. B.
Langdon, E. Cantú Paz, and et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference
(GECCO 2002). San Francisco, CA: Morgan Kaufmann Publishers, 2002, 415~21
[8] Gordon V., Bohm A. and Whitley D. . A note on the performance of genetic algorithms on zero-one knapsack
problems[C]. In: Proceedings of the 1994 ACM Symposium on Applied computing. New York NY: ACM Press,
1994, 194~195
[9] Richard Spillman. Solving Large Knapsack Problems with a Genetic Algorithm[C]. In: IEEE International
Conference on Systems, Man and Cybernetics, Intelligent Systems for the 21st Century. 1995, 632~637
[10] Martello Silvano, Toth Paolo. Knapsack problems: algorithms and computer implementations[M]. Chichester: J.
Wiley & Sons, 1990
[11] Kulanoot Araya. Algorithms for some hard knapsack problems[D]. Curtin University of Technology, Perth,
Western Australia, 2000
[12] 刘勇，康立山，陈毓屏. 非数值并行算法（第 2册）——遗传算法[M]. 北京：科学出版社，1995
[13] 徐宗本. 计算智能（第一册）——模拟进化计算[M]. 北京：高等教育出版社，2004
[14] 邢文训，谢金星. 现代优化计算方法[M]. 北京：清华大学出版社，1999
注 1：
注 2：GGA与 MT2等分别在主频相差约 倍的 CPU上计算，表 7~表 11的比较以此为准。另，两者的
SPECint2000值相差约 2倍。参见
-10-
中国科技论文在线
A greedy genetic algorithm for a class of the 0-1 knapsack
problems
Jin Huaiqun
Department of Mathematics and Information Technology, Hanshan Normal University, Chaozhou,
Guangdong, PRC, (521041)
Abstract
A new HGA for a class of 0-1KP called Greedy Genetic Algorithm is presented. GGA turns greedy
principle to advantage. The greedy approach is used for generating the first chromosome, and made use
of the greedy-operator to improve some feasible solutions further in the course of evolution. GGA uses
larger mutation probability and smaller crossover probability at the same time to overcome GA’s
limitation, mutation operation in GA plays an important and fundamental role in. Numerous
computational experiments have been carried out on about 400,000 well-structured new classes of
instances, and a comparative analysis with some recent state-of-art exact algorithms for the 0-1KP is
given. It is found that the average computing time of GGA grow to be less than the time of the exact
algorithms in company with an increase in coefficients. The average computing time to search for an
optimal solution is between and , and the average generation is 1 to 40.
Keywords: 0-1 knapsack problem, greedy algorithm, genetic algorithms, greedy genetic algorithm
