问题描述:
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背包问题。