本文目录一览：
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);
}
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/232551.html
微信扫一扫 
支付宝扫一扫 