部分背包问题

#include

struct lv

{

    double w;

    double v;

    double ov;

    int num;

    double isall;

};

void paixu(struct lv *a,int n);

void f(struct lv*a,int n,double c);

int main()

{

    int n,c;

    scanf("%d%d",&n,&c);

    struct lv a[n];

    for(int i=0;i

    {

        scanf("%lf%lf",&a[i].w,&a[i].v);

        a[i].ov=a[i].v/a[i].w;

        a[i].num=i;

        a[i].isall=0;

    }

    paixu(a,n);

    f(a,n,c);

    for(int i=0;i

    printf("%d: %fn",a[i].num,a[i].isall);

}

void paixu(struct lv a[],int n)

{

    for(int i=1;i

    {

        struct lv t=a[i];

        int j=i-1;

        while(j>=0&&a[j].ov

        {

            a[j+1]=a[j];

            --j;

        }

        a[j+1]=t;

    }

}

void f(struct lv*a,int n,double c)

{

    int i;

    for(i=0;i

    {

        if(a[i].w>c)

            break;

            a[i].isall=1;

            c-=a[i].w;

    }

    if(i

    a[i].isall=(c)/a[i].w;

}

eg2:

#include
struct bag
{
    int num;
    double w;
    double v;
    double m;
    double isall;

};

int main()
{
    int n , bc;
    scanf("%d %d",&n,&bc);
    struct bag a[n];
    for(int i=0;i     {

        scanf("%lf %lf",&a[i].w,&a[i].v);
        a[i].num=i;
        a[i].m=a[i].v/a[i].w;
        a[i].isall=0;
    }
    for(int i=0;i     {
        int min=i;
        for(int j=0;j         {
        if(a[j].m             min=j;
            struct bag b=a[min];
            a[min]=a[i];
            a[i]=b;
        }
    }
    int i;
    for(i=0;i     {
        if(a[i].w>bc)
            break;
            a[i].isall=1;
            bc-=a[i].w;
    }
    if(i     a[i].isall=(bc)/a[i].w;

    for(int i=0;i         printf("%d: %fn",a[i].num,a[i].isall);
}