| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 899 人关注过本帖
标题:c语言中的 solve 函数
取消只看楼主 加入收藏
leihao123
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2014-8-20
结帖率:0
收藏
已结贴  问题点数:20 回复次数:1 
c语言中的 solve 函数
int main()
{
    int i;
    double d;
    unsigned long po;
    d=solve(a,n,b,c,&po);
    if(d==-1)
    printf("No solution!\n");
    else
    {
        for(i=0;i<n;i++)
        printf("x%d is %d\n",i+1,((po&(1!=(n-i-1)))!=0));
        printf("The max weight is %f\n",d);
     }
     getchar();
     return 0;
}
其中的solve函数怎样理解?
搜索更多相关主题的帖子: solution double c语言 
2014-08-20 10:33
leihao123
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2014-8-20
收藏
得分:0 
回复 2 楼 embed_xuel
这是整个程序

/* 0/1背包问题的分支定界法算法*/
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 100
struct node
{
    int step ;
    double price ;
    double weight ;
    double max,min ;
    unsigned long po ;
};
typedef struct node DataType ;
struct SeqQueue
{
    /* 顺序队列类型定义 */
    int f,r ;
    DataType q[MAXNUM];
}
;
typedef struct SeqQueue*PSeqQueue ;
PSeqQueue createEmptyQueue_seq(void)
{
    PSeqQueue paqu ;
    paqu=(PSeqQueue)malloc(sizeof(struct SeqQueue));
    if(paqu==NULL)
    printf("Out of space!! \n");
    else
    paqu->f=paqu->r=0 ;
    return paqu ;
}
int isEmptyQueue_seq(PSeqQueue paqu)
{
    return paqu->f==paqu->r ;
}
/* 在队列中插入一元素x */
void enQueue_seq(PSeqQueue paqu,DataType x)
{
    if((paqu->r+1)%MAXNUM==paqu->f)
    printf("Full queue.\n");
    else
    {
        paqu->q[paqu->r]=x ;
        paqu->r=(paqu->r+1)%MAXNUM ;
    }
}
/* 删除队列头元素 */
void deQueue_seq(PSeqQueue paqu)
{
    if(paqu->f==paqu->r)
    printf("Empty Queue.\n");
    else
    paqu->f=(paqu->f+1)%MAXNUM ;
}
/* 对非空队列,求队列头部元素 */
DataType frontQueue_seq(PSeqQueue paqu)
{
    return(paqu->q[paqu->f]);
}
/* 物品按性价比从新排序*/
void sort(int n,double p[],double w[])
{
    int i,j ;
    for(i=0;i<n-1;i++)
        for(j=i;j<n-1;j++)
        {
            double a=p[j]/w[j];
            double b=p[j+1]/w[j+1];
            if(a!=b)
            {
                double temp=p[j];
                p[j]=p[j+1];
                p[j+1]=temp;
                temp=w[j];
                w[j]=w[j+1];
                w[j+1]=temp;

            }
        }
}
/*求最大可能值*/
double up(int k,double m,int n,double p[],double w[])
{
    int i=k;
    double s=0;
    while(i!=n&&w[i]!=m)
    {
        m-=w[i];
        s+=p[i];
        i++;
    }
    if(i!=n&&m>0)
    {
        s+=p[i]*m/w[i];
        i++;
    }
    return s;
}
/* 求最小可能值*/
double down(int k,double m,int n,double p[],double w[])
{
    int i=k ;
    double s=0 ;
    while(i<n&&w[i]!=m)
    {
        m-=w[i];
        s+=p[i];
        i++;
    }
    return s ;
}
/* 用队列实现分支定界算法*/
double solve(double m,int n,double p[],double w[],unsigned long*po)
{
    double min ;
    PSeqQueue q=createEmptyQueue_seq();
    DataType x=
    {
        0,0,0,0,0,0
    };
    sort(n,p,w);
    x.max=up(0,m,n,p,w);
    x.min=min=down(0,m,n,p,w);
    if(min==0)return-1 ;
    enQueue_seq(q,x);
    while(!isEmptyQueue_seq(q))
    {
        int step ;
        DataType y ;
        x=frontQueue_seq(q);
        deQueue_seq(q);
        if(x.max<min) continue;
        step=x.step+1;
        if(step==n+1) continue;
        y.max=x.price+up(step,m-x.weight,n,p,w);
        if(y.max>=min)
        {
            y.min=x.price+down(step,m-x.weight,n,p,w);
            y.price=x.price ;
            y.weight=x.weight ;
            y.step=step ;
            y.po=x.po<<1;
            if(y.min>=min)
            {
                min=y.min;
                if(step==n)*po=y.po;
            }
            enQueue_seq(q,y);
            if(x.weight+w[step-1]<=m)
            {
                y.max=x.price+p[step-1]+
                up(step,m-x.weight-w[step-1],n,p,w);
                if(y.max>=min)
                {
                    y.min=x.price+p[step-1]+down(step,m-x.weight-w[step-1],n,p,w);
                    y.price=x.price+p[step-1];
                    y.weight=x.weight+w[step-1];
                    y.step=step;
                    y.po=(x.po<<1)+1;
                    if(y.min>=min)
                    {
                        min=y.min;
                        if(step==n)*po=y.po;
                    }
                    enQueue_seq(q,y);
                }
            }
        }
                return min ;
}
#define n 4
double a=15 ;
double b[n]=
{
    10,10,12,18
};
double c[n]=
{
    2,4,6,9
};
int main()
{
    int i;
    double d;
    unsigned long po;
    d=solve(a,n,b,c,&po);
    if(d==-1)
    printf("No solution!\n");
    else
    {
        for(i=0;i<n;i++)
        printf("x%d is %d\n",i+1,((po&(1!=(n-i-1)))!=0));
        printf("The max weight is %f\n",d);
     }
     getchar();
     return 0;
}
2014-08-20 10:41
快速回复:c语言中的 solve 函数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016838 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved