您的位置:

数据结构c语言背包问题,C语言背包问题

本文目录一览:

C语言背包问题递归算法

你学过数据结构了吗?如果学过,那就比较好理解,该算法的思路和求二叉树的高度的算法的思路是十分类似的。把取这i个物体看成i个阶段,则该二叉树有i+1层。其中空背包时为根结点,左孩子则为放弃了第1个物品后的背包,右孩子为选取了第1个物品后的背包。今后在对第i个物品进行选择时,向左表示放弃,向右表示选取。则递归算法可如下:

int fun(int s, int i, int n) //s传入的是背包容量, i是进行第i个物品的选取,n为剩余物品的件数

{

if(s == 0) return 有解;

else if(剩余的每件物品都装不进|| n == 0) return 无解;

L = fun(s, i + 1, n - 1); //放弃第i个物品,则下一步的背包容量仍为s,然后看其是否有解,(递归调用进入左子树)

R = fun(s - wi, i + 1, n - 1); //选取第i个物品,则下一步的背包容量为s-wi,然后看其是否有解,(递归调用进入右子树)

return (l, r); //综合考虑左右两边,看哪边是正解或都无解。其实应该返回 return (L||R);

}

c语言的穷举法的背包问题

根据题目c1,c2是一组01组合的数组,也就是2个n位2进制数。

所以我的代码逻辑就是,c1,c2初值分别是 00000....以及111111....,之后循环执行c1+1;c2-1(2进制加减运算),最大执行次数 2的n次方-1(n位2进制数最大数)

代码实现功能,穷举所有可能方案,返回:第一个 /最后一个找到的可行方案。

函数int qj(BAG c1,BAG c2,int n,int *bws,int flag);

 当flag=1 返回第一个可行方案,flag=0 查找所有方案并返回最后一个可行方案

 我测试时,flag传值0,需要自己改!!

 由于迭代顺序,同样实验数据,返回的结构和你案例结构不一样,我在下图标注了。

#includestdio.h

#includemath.h

#includemalloc.h

#includestring.h

typedef struct bag

{

    int bweight;

    char *books;

}BAG;

int qj(BAG c1,BAG c2,int n,int *bws,int flag);//穷举所有n位2进制组合,返回最后一个可行方案(可能有多个方案)。

//参数:c1背包1,c2背包2,n书本个数,bws所有书本重量,标识:flag=1 找到第一个可行方案截止,flag=0查找所有方案

int checkOverLoad(BAG c1,BAG c2,int *bws,int n);

void add2(char *nums);//2进制字符串+1运算

void sub2(char *nums);//2进制字符串-1运算

int main()

{

    BAG c1,c2;

    int i,n,*bws,sum=0;

    printf("请输入两个背包的最大载重:\n");

    scanf("%d%d",c1.bweight,c2.bweight);

    printf("请输入书本的数量:\n");

    scanf("%d",n);

    c1.books=(char *)malloc(sizeof(char)*(n+1));

    c2.books=(char *)malloc(sizeof(char)*(n+1));

    c1.books[0]=0;

    c2.books[0]=0;

    bws=(int *)malloc(sizeof(int)*n);

    while(1)

    {

        sum=0;

        printf("请输入每本书的重量:\n");

        for(i=0;in;i++)

        {

            scanf("%d",bws[i]);

            sum+=bws[i];

        }

        if(sum=c1.bweight+c2.bweight)

            break;

        else

            printf("书本重量和超过背包负重和!请重新输入\n\n");

    }

    qj(c1,c2,4,bws,0);

//------------------------------打印结果-----------------------------

    printf("\n输出:\n");

    printf("book ");

    for(i=0;in;i++)

        printf("%d ",bws[i]);

    printf("\n");

    printf("c1 %s\n",c1.books);

    printf("c2 %s\n",c2.books);

}

int qj(BAG c1,BAG c2,int n,int *bws,int flag)// 穷举 所有n位二进制数,

{

    int i,max=(int)pow(2,n)-1;

    char *nums1,*nums2;

    nums1=(char *)malloc(sizeof(char)*(n+1));

    nums2=(char *)malloc(sizeof(char)*(n+1));

    printf("---------开始穷举所有可能的组合----------\n");

    memset(c1.books,'0',n);

    memset(c2.books,'1',n);

    c1.books[n]=c2.books[n]=0;

    printf("%s\n",c1.books);

    printf("%s\n",c2.books);

    if(checkOverLoad(c1,c2,bws,n)==0)

    {

        memset(nums1,0,n+1);

        memset(nums2,0,n+1);

        strcpy(nums1,c1.books);

        strcpy(nums2,c2.books);

        if(flag==1)

            return 0;

    }

    printf("\n");

    for(i=0;imax;i++)

    {

        add2(c1.books);

        sub2(c2.books);

        printf("%s\n",c1.books);

        printf("%s\n",c2.books);

        if(checkOverLoad(c1,c2,bws,n)==0)

        {

            memset(nums1,0,n+1);

            memset(nums2,0,n+1);

            strcpy(nums1,c1.books);

            strcpy(nums2,c2.books);

            if(flag==1)

                return 0;

        }

        printf("\n");

    }

    printf("-----------------穷举结束------------------\n");

    memset(c1.books,0,n+1);

    memset(c2.books,0,n+1);

    strcpy(c1.books,nums1);

    strcpy(c2.books,nums2);

    free(nums1);

    free(nums2);

    return 0;

}

void add2(char *nums)//2进制字符串加1

{

    int i,n=strlen(nums),jin=0;

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

    {

        if(nums[i]=='0'  i==n-1)

        {

            nums[i]='1';

            break;

        }

        else if(nums[i]-'0'+jin==1  in-1)

        {

            nums[i]='1';

            break;

        }

        else

        {

            jin=1;

            nums[i]='0';

        }

    }

}

void sub2(char *nums)//2进制字符串减1

{

    int i,n=strlen(nums),j=0;

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

    {

        if(nums[i]=='1'  i==n-1)

        {

            nums[i]='0';

            break;

        }

        else if(nums[i]-'0'-j==0  i!=n-1)

        {

            nums[i]='0';

            break;

        }

        else

        {

            nums[i]='1';

            j=1;

        }

    }

}

int checkOverLoad(BAG c1,BAG c2,int *bws,int n)//检查是否超载。超载返回1,否返回0

{

    int i,sum1=0,sum2=0;

    for(i=0;in;i++)

        if(c1.books[i]=='1')

            sum1=sum1+bws[i];

        else

            sum2=sum2+bws[i];

    if(sum1c1.bweight)

    {

        printf("背包1超载!\n");

        return 1;

    }

    if(sum2c2.bweight)

    {

        printf("背包2超载!\n");

        return 1;

    }

    printf("方案可行!\n");

    return 0;

}

C语言:背包问题(数据结构)

详细程序代码如下:

用VC6.0编译.保存代码时,以.C为后缀名

下面是一组测试数据:

请输入背包能容纳的最大重量:20

请输入物品个数:10

请输入每一个物品的重量和价值:1,11,2,22, 3,33.....10,100

结果是正确的.

#includestdio.h

#includeconio.h

#includemalloc.h

#define NUMBER 20/*最大物品数量*/

#define TRUE 1

#define FALSE 0

struct Record/*本结构体用于保存每一次结果*/

{

int totalWeight;/*本次结果的总价值*/

int goods[NUMBER];/*本次结果对应的下标*/

struct Record *next;

};

struct Record *headLink;

struct Record result;

int stack[NUMBER];

int top;

int weight[NUMBER];/*保存物品重量的数组*/

int value[NUMBER];/*保存对应(下标相同)物品的价值*/

int knapproblen(int n,int maxweight,int weight[]);

void CreateHeadLink(void);

struct Record *MallocNode(void);

void InsertOneNode(struct Record *t);

void GetResult(void);

void ShowResult(void);

void main()

{

int n,i;

int maxWeight;/*背包能容纳的最大重量*/

printf("请输入背包能容纳的最大重量:\n");

scanf("%d",maxWeight);

printf("请输入物品个数:\n");

scanf("%d",n);

printf("请输入每一个物品的重量和价值:\n");

for(i=0;in;i++)

{

printf("请输入第%d个物品重量\n",i+1);

scanf("%d",(weight[i]));

printf("请输入第%d个物品价值\n",i+1);

scanf("%d",(value[i]));

}

if(knapproblen(n,maxWeight,weight)==TRUE)/*调用背包处理函数,如果成功就输出“答案”*/

{

GetResult();/*遍历链表,查找最佳的结果*/

ShowResult();/*显示结果*/

}

free(headLink);

getch();

}

/*调用背包处理函数*/

int knapproblen(int n,int maxweight,int weight[])

{

struct Record *p;

int i=1,j;

int tempTop=0;

top=0;/*先赋栈指针为0*/

CreateHeadLink();/*先建立链头*/

while((maxweight0)(i=n))/*当还可以装下物品,且物品没有用完时*/

{

if((maxweight-weight[i]==0)||(maxweight-weight[i]0)(in))/*正好装完物品或还能容纳物品且物品没有用完时*/

{

stack[++top]=i;/*把对应物品的处标保存到栈中*/

p=MallocNode();/*每一次得到一个结果后,就将该结果保存到链表中*/

for(tempTop=top,j=0;tempTop0;tempTop--,j++)

{

p-totalWeight+=value[stack[tempTop]];/*得到本次结果的总价值*/

p-goods[j]=stack[tempTop];/*得到本次结果对应的物品下标*/

}

InsertOneNode(p);/*加到链表中*/

maxweight=maxweight-weight[i];

}

if(maxweight==0)/*能装入包中*/

{

return TRUE;

}

else if((i==n)(top0))/*继续测试*/

{

i=stack[top];

top=top-1;

maxweight=maxweight+weight[i];

}

i++;

}

return FALSE;

}

/************************************

函数功能:建立链表表头

************************************/

void CreateHeadLink(void)

{

struct Record *p;

p=(struct Record*)malloc(sizeof(struct Record));

headLink=p;

p-next=NULL;

}

/************************************

函数功能:申请一个新结点,并将其初始化

************************************/

struct Record *MallocNode(void)

{

struct Record *p;

int i;

p=(struct Record*)malloc(sizeof(struct Record));

if(p==NULL)

return NULL;

p-totalWeight=0;/*初始化总价值为0*/

for(i=0;iNUMBER;i++)

p-goods[i]=-1;/*初始化下标为-1,即无效*/

p-next=NULL;

return p;

}

/************************************

函数功能:在链表的结尾处增加一个结点

************************************/

void InsertOneNode(struct Record *t)

{

struct Record *p;

p=headLink;

while(p-next)

{

p=p-next;

}

p-next=t;

}

/************************************

函数功能:遍历链表,找总价值最大的结点保存到

result中

************************************/

void GetResult(void)

{

struct Record *p;

int i;

result.totalWeight=headLink-next-totalWeight;/*先将第一个结点当作"最佳"结果*/

for(i=0;iNUMBER;i++)

{

if(headLink-next-goods[i]==-1)

break;

result.goods[i]=headLink-next-goods[i];

}

p=headLink-next-next;

while(p)/*查找最佳结果*/

{

if(p-totalWeightresult.totalWeight)/*如果发现p点价值比当前结果还大,则将p又作为最佳结果*/

{

result.totalWeight=p-totalWeight;

for(i=0;iNUMBER;i++)

result.goods[i]=-1;

for(i=0;iNUMBER;i++)

{

if(p-goods[i]==-1)

break;

result.goods[i]=p-goods[i];

}

}

p=p-next;

}

}

/***************************

显示最佳结果

*******************************/

void ShowResult(void)

{

int i;

printf("最佳装载如下:\n");

for(i=0;iNUMBER;i++)

{

if(result.goods[i]==-1)

break;

printf("weight[%d]=%d\tvalue[%d]=%d\t",result.goods[i],weight[result.goods[i]],result.goods[i],value[result.goods[i]]);

if((i+1)%2==0)

printf("\n");

}

printf("\n总价值是:\n%d",result.totalWeight);

}

C语言 背包问题 递归算法

提问者的这程序中用了递归算法,不过逻辑上有个小bug,就是在判断到n==0时,如果还有容量,那么返回的应该是第一个物品的重量而不是0。你可以改变容量C或物品参数来检验算法的逻辑正确性。

关于输出选择的物品,我加了一个数组,用来标记选择的物品。因为做完所有递归后只有最外层的标记是有效的,所以最后用了一个for循环来完成各层的标记。下面是改动后的程序:

    int a[5]={0};

int MaxW(int n, int C, int *Volunme, int *Weight)

{

int W=0,W1=0,W2=0;

if (n == 0)

{

if(C = Volunme[0])

{

a[0]=1;

return W=1;

}

else

return 0;

}

else if(C = Volunme[n])//背包剩余空间可以放下物品n

{

W1 = MaxW(n-1, C-Volunme[n],Volunme,Weight) + Weight[n]; //放入n所能得到的重量

W2 = MaxW(n-1,C,Volunme,Weight); //不放n所能得到的重量

W=(W1W2?W1:W2);

a[n]=(W1W2?1:0);

}

else//背包空间放不下n,返回判断放n-1的情况

{

return MaxW(n-1,C,Volunme,Weight);

}

return W;

}

int main(void)

{

int n=5;int C=7;

int Volunme[] = {1,2,3,4,5};

int Weight[] = {1,2,5,7,8};

printf("最大重量为%d\n",MaxW(n-1,C,Volunme,Weight));

for(int i=n-2;i=0;i--)

{

a[i]=0;

if(a[i+1]==1)

{

C-=Volunme[i+1];

Weight[i+1]=0;

}

MaxW(i,C,Volunme,Weight);

}

printf("选择的物品号是:");

for(int i=0;i5;i++)

{

if(a[i]==1)

printf("#%d  ",i+1);

}

printf("\n");

return 0;

}

背包问题(C语言)

我copy一下别人的递归算法,假如你有时间限时的话,那我就用动态规划帮你重新code一个

#include stdio.h

#define N 100 //物品总种数不是常量,没法根据它来决定数组的长度,只有先定义个长度了

int n;//物品总种数

double limitW;//限制的总重量

double totV;//全部物品的总价值

double maxv;//解的总价值

int option[N];//解的选择

int cop[N];//当前解的选择

struct {//物品结构

double weight;

double value;

}a[N];

//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值

void find(int i,double tw,double tv)

{

int k;

//物品i包含在当前方案的可能性

if(tw+a[i].weight = limitW){

cop[i]=1;

if(in-1)find(i+1,tw+a[i].weight,tv);

else{

for(k=0;kn;++k)

option[k]=cop[k];

maxv=tv;

}

}

cop[i]=0;

//物品i不包含在当前方案的可能性

if(tv-a[i].valuemaxv){

if(in-1)find(i+1,tw,tv-a[i].value);

else{

for(k=0;kn;++k)

option[k]=cop[k];

maxv=tv-a[i].value;

}

}

}

void main()

{

int k;

double w,v;

printf("输入物品种数:");

scanf("%d",n);

printf("输入各物品的重量和价值:");

for(totV=0.0,k=0;kn;++k){

scanf("%lf %lf",w,v);

a[k].weight = w;a[k].value = v;

totV += v;

}

printf("输入限制重量:");

scanf("%lf",limitW);

maxv=0.0;

for(k=0;kn;++k)cop[k]=0;

find(0,0.0,totV);

for(k=0;kn;++k)

if(option[k])printf("%4d",k+1);

printf("总价值为: %2f",maxv);

}