编辑代码

#include <stdio.h>

int main()
{
    printf("************贪处算法解决背包问题****************\n "); //标题
    float m , w[100], p[1000], P[1000], s , pp =0; //设置变量 
    int n , i, j, b[50], max;
    printf ("     请输入货物的总类别数及背包的最大总容量\n"); 
    printf ("货物的总类别数：");
    scanf ("%d",& n );
    printf ("背包的最大总容量：");
    scanf ("%f",& m );
    for (i=1, s=0; i <= n; i ++)//算出货物的总重量 s 
    {
        printf ("货物的编号：% d\n重量：",i); 
        scanf ("%f",&w[i]);
        printf ("价值："); 
        scanf ("%f",&p[i]);
        P[i] = p[i];
        s = s + w[i];
    }
    if ( s <= m ) //货物的总重量如果小于 m,则全装入
    {
        for (i=1; i <= n ; i ++) 
        {
            pp += p[i];
        }
        printf ("选择的结果是：货物的总重量小于背包的容量故全装入背包，得到的总利润是：% f\n ",pp );
        return 0;
    }
    
    printf ("选择的结果是:\n");//当物品的总重量大于 m 时的情况 
    for (i=1; i <= n ; i ++)
    {
        max = 1 ; 
        for ( j =2; j <= n;j ++)
        {
            //比较物品的单位价值
            if (P[j] /w[j] > P[max] /w[max])
            {
                max=j;
            }
            P[max]=0;  //标记已经排了序的物品
            b[i]= max;
        }
    }
    for ( i =1, s=0; s < m && i<= n ; i ++)
    {
        s= s + w [b[i]];
        float W = w [b[i-1]];
        if (s!= m)  //超出背包容量
        { 
            w [b[i-1]]= m -( s - w[b[i-1]]);  //装入第 b [i-1］个物品的重量
            p[b[i-1]]= w[b[i-1]] / W * p[b[i-1]];  //装入第 b [i-1]个物品的价值
        }
        for(j =1;j<=i-1;j++) //输出选取的结果
        {
            printf ("物品的编号：%d ，可装入该物品的重量：%f \n", b[j], w[b[j]]);
            pp += p[b[j]];
        }
    }
     
    printf("总价值%f\n",pp); //装入背包的物品的总价值
    return 0;
}