遗传算法解决0-1背包问题

问题描述:

0-1背包问题说的是,给定背包容量W,一系列物品{weiht,value},每个物品只能取一件,获取背包所能容纳的value最大值。

比如说:背包容量300,物品数量10.有以下物品:{weight,value}

95 89
75 59
23 19
73 43
50 100
22 72
6 44
57 16
89 7
98 64

最佳组合:

95 89
23 19
50 100
22 72
6 44
98 64

总重量:294,总价值388。

算法:

遗传算法:https://baike.baidu.com/item/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95/838140?fr=aladdin

遗传算法主要有以下几个步骤

  • 初始化种群
  • 种群适应度计算
  • 种群选择
  • 种群交配
  • 种群变异

第五步完成又又跳转到第二部迭代计算,直到达到收敛条件。

直接上代码:https://github.com/Yves-yuan/backpack-scala

用遗传算法解决0-1背包问题。

上一篇:Java基础95 待续


下一篇:【西北师大-19软工】第一次作业成绩汇总