遗传算法的0-1背包问题(c语言)

基于遗传算法的0-1背包问题的求解摘要：一、前言组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源

0-1 基于遗传算法的背包问题的求解 摘要： 一、前言 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅 在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛 的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可 以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在 NP 有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于完全问题， 如何求解其最优解或是近似最优解便成为科学的焦点之一。 遗传算法已经成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生 物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性 21 强、适应并行处理以及应用范围广等特点，奠定了作为世纪关键智能计算的地 位。 NP- 背包问题是一个典型的组合优化问题，在计算理论中属于完全问题，其 w[i]i 计算复杂度为，传统上采用动态规划来求解。设是经营活动所需要 Mp[i]i 的资源消耗，是所能提供的资源总量，是人们经营活动得到的利润或收益， 则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 二、问题描述 (KnapsackProblem)nweight 背包问题的一般提法是：已知个物品的重量（） profitcontain 及其价值（或收益）分别为和，背包的容量（）假设 设为，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内 所装物品的价值最大？ 0/1 该问题的模型可以表示为下述整数规划模型： 目标函数： * （）