1背包问题算法的C语言程序；背包问题描述\x05现有n种物品

思路是：

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

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

你应该能看懂.

#include

#include

#include

#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=0;ii;j--)

{

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=0;ilimit)// 如果目前所有放进去的东西的重量大于限制的重量,就不放东西了

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=0;i

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-22994-1.html