c语言背包问题(C语言 贪心算法求背包问题)
大家好,今天小编来为大家解答以下的问题，关于c语言背包问题，C语言 贪心算法求背包问题这个很多人还不知道，现在让我们一起来看看吧！
c语言的穷举法的背包问题
根据题目c1，c2是一组01组合的数组，也就是2个n位2进制数。
所以我的代码逻辑就是，c1，c2初值分别是00000....以及111111....，之后循环执行c1+1；c2-1（2进制加减运算），最大执行次数2的n次方-1（n位2进制数最大数）
代码实现功能，穷举所有可能方案，返回:第一个/最后一个找到的可行方案。
函数intqj(BAGc1,BAGc2,intn,int*bws,intflag);
当flag=1返回第一个可行方案，flag=0查找所有方案并返回最后一个可行方案
我测试时，flag传值0，需要自己改！！
由于迭代顺序，同样实验数据，返回的结构和你案例结构不一样，我在下图标注了。
#include<stdio.h>
#include<math.h>
#include<malloc.h>
#include<string.h>
typedefstructbag
{
intbweight;
char*books;
}BAG;
intqj(BAGc1,BAGc2,intn,int*bws,intflag);//穷举所有n位2进制组合，返回最后一个可行方案（可能有多个方案）。
//参数：c1背包1，c2背包2，n书本个数，bws所有书本重量，标识：flag=1找到第一个可行方案截止，flag=0查找所有方案
intcheckOverLoad(BAGc1,BAGc2,int*bws,intn);
voidadd2(char*nums);//2进制字符串+1运算
voidsub2(char*nums);//2进制字符串-1运算
intmain()
{
BAGc1,c2;
inti,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;i<n;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;i<n;i++)
printf("%d",bws[i]);
printf("\n");
printf("c1%s\n",c1.books);
printf("c2%s\n",c2.books);
}
intqj(BAGc1,BAGc2,intn,int*bws,intflag)//穷举所有n位二进制数,
{
inti,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)
return0;
}
printf("\n");
for(i=0;i<max;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)
return0;
}
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);
return0;
}
voidadd2(char*nums)//2进制字符串加1
{
inti,n=strlen(nums),jin=0;
for(i=n-1;i>=0;i--)
{
if(nums[i]=='0'&&i==n-1)
{
nums[i]='1';
break;
}
elseif(nums[i]-'0'+jin==1&&i<n-1)
{
nums[i]='1';
break;
}
else
{
jin=1;
nums[i]='0';
}
}
}
voidsub2(char*nums)//2进制字符串减1
{
inti,n=strlen(nums),j=0;
for(i=n-1;i>=0;i--)
{
if(nums[i]=='1'&&i==n-1)
{
nums[i]='0';
break;
}
elseif(nums[i]-'0'-j==0&&i!=n-1)
{
nums[i]='0';
break;
}
else
{
nums[i]='1';
j=1;
}
}
}
intcheckOverLoad(BAGc1,BAGc2,int*bws,intn)//检查是否超载。超载返回1，否返回0
{
inti,sum1=0,sum2=0;
for(i=0;i<n;i++)
if(c1.books[i]=='1')
sum1=sum1+bws[i];
else
sum2=sum2+bws[i];
if(sum1>c1.bweight)
{
printf("背包1超载！\n");
return1;
}
if(sum2>c2.bweight)
{
printf("背包2超载！\n");
return1;
}
printf("方案可行！\n");
return0;
}
C语言:背包问题(数据结构)
详细程序代码如下:
用VC6.0编译.保存代码时,以.C为后缀名
下面是一组测试数据:
请输入背包能容纳的最大重量：20
请输入物品个数：10
请输入每一个物品的重量和价值：1,11,2,22, 3,33.....10,100
结果是正确的.
#include<stdio.h>
#include<conio.h>
#include<malloc.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;i<n;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((maxweight>0)&&(i<=n))/*当还可以装下物品，且物品没有用完时*/
{
if((maxweight-weight[i]==0)||(maxweight-weight[i]>0)&&(i<n))/*正好装完物品或还能容纳物品且物品没有用完时*/
{
stack[++top]=i;/*把对应物品的处标保存到栈中*/
p=MallocNode();/*每一次得到一个结果后，就将该结果保存到链表中*/
for(tempTop=top,j=0;tempTop>0;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)&&(top>0))/*继续测试*/
{
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;i<NUMBER;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;i<NUMBER;i++)
{
if(headLink->next->goods[i]==-1)
break;
result.goods[i]=headLink->next->goods[i];
}
p=headLink->next->next;
while(p)/*查找最佳结果*/
{
if(p->totalWeight>result.totalWeight)/*如果发现p点价值比当前结果还大，则将p又作为最佳结果*/
{
result.totalWeight=p->totalWeight;
for(i=0;i<NUMBER;i++)
result.goods[i]=-1;
for(i=0;i<NUMBER;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;i<NUMBER;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语言 贪心算法求背包问题
是你的冒泡排序出了问题~
你吧原来的1-2-3号按照东西的价值重新排列现在的1-2-3对应原来的2-1-3了
所以你输出的时候是按 1-2-3输出的话就等于第一个是原来的X2第二个是X1第三个是X3
而且你的冒泡排序用错了只比较了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去学校帮你重新改改我家的机器没有C++
周一晚上我会上传答案~我最近正好也要做算法的作业~
#include<stdio.h>
#include<math.h>
#define N 50
float find(float p[N],float w[N],float x[N],float M,int n)/*先放单位价值量大的物体，再考虑小的物体*/
{
int i;
float maxprice;
for(i= 0; i< n; i++)
x[i]= 0;
i= 0;
maxprice=0;
while(i< n&& w[i]< M)
{
M=M-w[i];
x[i]=w[i];/*表示放入数量*/
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if(i< n&&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}
int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(
感谢您花时间阅读本文！我们希望通过对c语言背包问题和C语言 贪心算法求背包问题的问题进行探讨，为您提供了一些有用的见解和解决方案。如果您需要更多帮助或者有其他疑问，请不要犹豫与我们联系。