分布估计算法求解0-1背包问题算法的C语言程序；背包问题描述\x05现有n种物品,对,已知第i种物品的重量为正整数,价值为正整数,背包能承受的最大载重量为正整数W,现要求找出这n种物品的一

分布估计算法求解0-1背包问题算法的C语言程序；背包问题描述\x05现有n种物品,对,已知第i种物品的重量为正整数,价值为正整数,背包能承受的最大载重量为正整数W,现要求找出这n种物品的一
分布估计算法求解0-1背包问题算法的C语言程序；
背包问题描述
\x05现有n种物品,对,已知第i种物品的重量为正整数,价值为正整数,背包能承受的最大载重量为正整数W,现要求找出这n种物品的一个子集,使得子集中物品的总重量不超过W且总价值尽量大.对每种物品只有两种选择,可以选择放与不放.即当物件被选入背包时,定义变量=1,否则=0.

分布估计算法求解0-1背包问题算法的C语言程序；背包问题描述\x05现有n种物品,对,已知第i种物品的重量为正整数,价值为正整数,背包能承受的最大载重量为正整数W,现要求找出这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