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

在背包问题中,需对容量为s的背包进行装载。从n个物品中选取装入背包的物品,物品i的重量为wi,价值为pi。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装... 在背包问题中,需对容量为s 的背包进行装载。从n 个物品中选取装入背包的物品,物品i 的重量为wi,价值为pi。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。请找出背包问题的一个求解方案。
请利用动态规划,写出完整的程序(最好附有文字说明)。谢谢,这是一个project,希望程序越详细越好,考虑得越完整越好。满意的有追加!!!
一楼的麻烦看清楚题目,每个物品都有其重量和价值,要在重量允许范围内达到最大价值
展开
 我来答
SSHHFF凤
2008-05-26 · TA获得超过1690个赞
知道小有建树答主
回答量:799
采纳率:83%
帮助的人:334万
展开全部
详细程序代码如下:
用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);
}
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式