分布估计算法简介

这类算法知其然不知其所以然，仅作大概介绍，如果后续学习的话再补充详细。

分布估计算法是一种全局搜索算法，也是一种进化算法，传统的遗传算法通过所谓的遗传算子喊漏，选择、交叉、变异来实现进化；而分布估计算法用概率模型来描述解在空间的分布，通过选择较优的解来更新概率描述解的概率向量，进而概率的产生新的解（采样）直至达到最郑拿烂优或敏或已设置的迭代次数。通过上述步骤寻找全局最优解。

打个比方，我每天不知到吃啥，第一周我在后街随便吃了10家店，觉得ABCD这四家店很好吃，那么第二周的时候我更可能选择ABCD这四家店及其旁边的店，这这周发现ABE这几家好吃，然后下周我更可能去这几家店及其旁边的店，周而复返最后得出B家最好吃。

连续域的分布估计算法一般采用高斯分布或者高斯核来描述解空间的概率分布。

思路是：

1、先将所有型哪东西按价值和重量的比值（价重樱租前比）从大到小排列。这里我用的冒泡排序。

2、将价重比大的先放到背包里。直到背包不能再放为止。此时价格就是最大的。

你应该能看懂。

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define LIMIT 100

#define TN 20

typedef struct{

int weight//东西的重量

int value // 东西的价值

int selected // 是否放进去

}Things

void swap_things(Things *t1, Things *t2) // 只是一个交换函数而已。

{

int weight, value, selected

weight=t1->weight

value=t1->value

selected=t1->selected

t1->weight=t2->weight

t1->value=t2->value

t1->selected=t2->selected

t2->weight=weight

t2->value=value

t2->selected=selected

}

void sort_things(Things t[], int n) // 排序函数，按照价重比排序（价格与重量的比值）

{

int i,j

double vpw1=0, vpw2=0

for(i=0i<n-1i++)

{

for(j=n-1j>ij--)

{

vpw1=(double)t[j].value/t[j].weight //求出第 j 个东西的价重比

vpw2=(double)t[j-1].value/t[j-1].weight // 求出第j-1个东西的价重比

if(vpw1>vpw2) // 如果第 j 个的价重比大于 第 j-1个价重比，则将这两个东西的位置调换一下。

swap_things(&t[j],&t[j-1])

}

}

}

void select_things(Things t[], int n, int limit) // 这个函数用来选择要放进去的东西

{

int w=0, v=0,i

for(i=0i<ni++)

{

if(w+t[i].weight>limit) // 如果目前所有放进去的东西的重量大于限制的重量，就不放东西了

break

w+=t[i].weight //脊清 计算目前所有放进去的东西的重量

v+=t[i].value// 计算目前所有放进去的东西的价格

t[i].selected=1 // 把这个东西标记为放进去了

}

printf("totel: weight=%d, value=%d\n",w,v) // 打印放进去的东西的总重量和总价格

}

int main(void)

{

Things t[TN]

int i

srand((unsigned)time(NULL))

for(i=0i<TNi++)// 初始化所有的东西的重量和价格

{

t[i].weight=rand()%TN+1

t[i].value=rand()%TN+1

t[i].selected=0

}

sort_things(t,TN)

select_things(t,TN,LIMIT)

printf("weight\tvalue\tselected\n")

for(i=0i<TNi++) // 打印所有东西的重量、价格和是否放进去。

printf("%d\t%d\t%d\n",t[i].weight,t[i].value,t[i].selected)

return 0

}

---