#include?

struct?goodinfo
{
?float?p;?//物品效益
?float?w;?//物品重量
?float?X;?//物品該放的數量
?int?flag;?//物品編號
};//物品信息結構體


void?Insertionsort（goodinfo?goods[]int?n）
{
?int?ji;
?for（j=2;j<=n;j++）
?{
??goods[0]=goods[j];
?????i=j-1;
??

??while?（goods[0].p>goods[i].p）
??{
???goods[i+1]=goods[i];
???i--;
??}
??goods[i+1]=goods[0];
?}

}//按物品效益，重量比值做升序排列


void?bag（goodinfo?goods[]float?Mint?n）
{?
?
?float?cu;
?int?ij;
?for（i=1;i<=n;i++）
??goods[i].X=0;
?cu=M;??//背包剩余容量
?for（i=1;i?{
??if（goods[i].w>cu）//當該物品重量大與剩余容量跳出
???break;
??
???goods[i].X=1;
???cu=cu-goods[i].w;//確定背包新的剩余容量
?}
?if（i<=n）
??goods[i].X=cu/goods[i].w;//該物品所要放的量

/*按物品編號做降序排列*/?
?for（j=2;j<=n;j++）
?{
??goods[0]=goods[j];
?????i=j-1;
??

??while?（goods[0].flag??{
???goods[i+1]=goods[i];
???i--;
??}
??goods[i+1]=goods[0];
?}
////////////