b4.txt

背包问题 采用分枝限界法解决0/1背包问题! 本人上机实习作业,通过老师验收,合格! 针对部分上机实习的同学可以来下~

#include

#define n 4

double m=15;

double w[]={2,4,6,9};

double p[]={10,10,12,18};

int x[n];

int x1[n];

double max=0;

double totalweight=0;

 

void solve(int i){

    if(i==n){

        int i;double sum;

        for(sum=0,i=0;i             sum+=x1*p;

        if(sum>max){

            max=sum;

            for(i=0;i                 x=x1;

        }

        return;

    }

    x1=0;/* 将x置为0 */

    solve(i+1);

    if(totalweight+w<=m){

        x1=1;/* 将x置为1 */

        totalweight+=w;

        solve(i+1);

        totalweight-=w;

    }

}

int main(){

    int i;

    solve(0);

    for(i=0;i         printf("x%d=%d  ",i+1,x);

    return 0;

}

/* 0/1背包问题的动态规划法算法*/

#include

#include

#define ymax 100

#define nmax 100

float f[nmax][ymax];

void Knapsack(float p[],int w[],int c,int n)

{

    int y=0,i=0;

    for(y=0;y         f[n][y]=0;

    for(y=w[n];y<=c;y++)

        f[n][y]=p[n];

 

    for(i=n-1;i>1;i--)

    {

        for(y=0;y             f[y]=f[i+1][y];

        for(y=w;y<=c;y++)

            f[y]=(f[i+1][y]>(f[i+1][y-w]+p))?f[i+1][y]:(f[i+1][y-w]+p);

    }

    f[1][c]=f[2][c];

    if(c>=w[1])

        f[1][c]=(f[1][c]>(f[2][c-w[1]]+p[1]))?f[1][c]:(f[2][c-w[1]]+p[1]);

}

void traceback(int w[],int c,int n,int x[])

{

    int i=0;

    for(i=1;i         if(f[c]==f[i+1][c])

            x=0;

        else

        {

            x=1;

            c-=w;

        }

        x[n]=f[n][c]?1:0;

}

int main()

{

    float s=0,temp=0; float  *p;

    int m=0,n=0,i=0,*w,*x;

    printf("please input the maximum weight of the bag:nm=");

    scanf("%d",&m);

    printf("please input the number of objects:nn=");

    scanf("%d",&n);

    p=(float*)malloc((n+1)*sizeof(float));

    printf("please input  the prices of all the objects:n");

    for(i=1;i<=n;i++)

        scanf("%f",p+i);

    w=(int*)malloc((n+1)*sizeof(int));

    printf("please input  the weight of all the objects:n");

    for(i=1;i<=n;i++)

        scanf("%d",w+i);

    

    x=(int*)malloc((n+1)*sizeof(int));

    Knapsack(p,w,m,n);

    traceback(w,m,n,x);

    s=f[1][m];

    printf("the max value is %fn",s);/*输出*/

    for(i=1;i<=n;i++)

    {

        if(x==1)

        {

            printf("     the p:  %f",p);

            printf("     the w:  %dn",w);

        }

    }

    return 0;

}