普通背包 贪心算法c

#include<stdio.h>   
 
void package_part(int *w,int *v,double *p,int n,int c,int *flag)  
{  
    int i,j,temp;
    double tempD,totalValue = 0.0;
    
    //计算单位
    for(i=0;i<n;i++)
    {
        p[i] = (double)v[i] / (double)w[i];
        flag[i] = i;
    }
    //根据单价排序,flag数组保存物品的下标
    for(i=0;i<n;i++)
    {
        for(j=n-1;j>i;j--)
        {
            if(p[j] > p[j-1])
            {
                temp = flag[j];
                flag[j] = flag[j-1];
                flag[j-1] = temp;    
                
                tempD = p[j];
                p[j] = p[j-1];
                p[j-1] = tempD;
            }
        }
    }
    //̰贪心法得出应该装入的物品    
    for(i=0;i<n;i++)
    {
        if(c >= w[flag[i]])
        {
            totalValue += v[flag[i]];
            c -= w[flag[i]];
            printf("第%d号物品整个放入
",flag[i]);
        }else
        {
            totalValue += p[flag[i]] * (double)c / (double) w[flag[i]];
            printf("第%d号物品放入了%f
",flag[i],(double)c / (double) w[flag[i]]);
            break;
        }
    }
    printf("总价值为：%f",totalValue);
}  
 
void main()  
{  
    int c, n ; 

    printf("请输入背包的最大容量:");
    scanf("%d",&c);

    printf("输入物品数:");
    scanf("%d",&n);

 int *w=(int *)malloc(n*sizeof(int));
    int *v=(int *)malloc(n*sizeof(int)); 
    
    
    printf("请分别输入物品的重量:");
    for(int i=0;i<n;i++)
        scanf("%d",&w[i]);
 
    printf("请分别输入物品的价值ֵ:");
    for(int i=0;i<n;i++)
        scanf("%d",&v[i]);

    
    double p[] = {0};  //每个物品的单位价值  
    int flag[10];   //用于排序
    package_part(w,v,p,n,c,flag);  
}