Matlab 中文论坛首发：www.iLoveMatlab.cn
用粒子群算法解决 0/1 背包问题
背包问题( Knapsack Problem)是著名的 NP 问题，也是一个典型的组合优化问
题。这里要解决的背包问题的描述如下：
ai：第i个物品的体积；
ci：第i个物品的价值；
b：背包的重量限制；
背包问题就是在总的体积有限的条件下,追求总价值最大的有效资源分配问
题。有界的整数背包问题可转化成等价的 0-1 背包问题，定义变量
粒子群算法速度和位置的迭代公式为：
背包问题中的 X 是一个 0-1 序列，每一个粒子的位置可以用向量 X 来表示，粒
子的位置就表示一个可行解，粒子的适应值函数就可以表示为
粒子群算法的寻优可以表示为求取使得 f (X)值最大的 X
粒子群中的速度定义为物品选择的变换集，即为两次位置的距离，用 V 表
示，则|V|表示速度所含的交换的数目，从而该速度可定义为
以此作为用粒子群算法解决背包问题的切入点，待解决的背包问题如下所示：
- 1
- 2
- 3
前往页