首页 > 程序开发 > 软件开发 > C语言 >

C语言学习趣事_数据结构_经典命题_1_背包问题_分析_1

2011-07-25

昨天测试了一下,如何通过函数从程序的堆栈空间来申请空间供其他函数使用, 里面提到了一个数据结构的命题:背包问题。命题如下:View Code/* 1.问题描述 假设有一个能装入总体积为T的背包和n件体积分别为w1...

昨天测试了一下,如何通过函数从程序的堆栈空间来申请空间供其他函数使用, 里面提到了一个

数据结构的命题:背包问题。

命题如下:

View Code

/* 1.问题描述 假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品, 能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wm=T, 要求找出所有满足上述条件的解。 例如: 当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解: (1,4,3,2) (1,4,5) (8,2) (3,5,2)。2.实现提示 可利用回溯法的设计思想来解决背包问题。首先,将物品排成一列,然后, 顺序选取物品装入背包,若已选取第i件物品后未满,则继续选取第i+1件, 若该件物品“太大”不能装入,则弃之,继续选取下一件,直至背包装满为止。 如果在剩余的物品中找不到合适的物品以填满背包,则说明“刚刚”装入的物品 “不合适”,应将它取出“弃之一边”,继续再从“它之后”的物品中选取,如此 重复,直到求得满足条件的解,或者无解。 由于回溯求解的规则是“后进先出”,自然要用到“栈”。3.进一步考虑: 如果每件物品都有体积和价值,背包又有大小限制,求解背包中存放物 品总价值最大的问题解---最优解或近似最优解。*/

今天按照里面的方法来进行测试,已经实现了部分代码, 并且可以测试部分结果,但是还没有完全实现,

现在将代码贴出来供各位大侠点评,本来想今天弄出来的,但是因为明天要上班,同时今天下班有点晚(下班的

时候已经7点半了,)。

明天在继续将剩下的部分实现。

View Code

/* 1.问题描述 假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品, 能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wm=T, 要求找出所有满足上述条件的解。 例如: 当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解: (1,4,3,2) (1,4,5) (8,2) (3,5,2)。2.实现提示 可利用回溯法的设计思想来解决背包问题。首先,将物品排成一列,然后, 顺序选取物品装入背包,若已选取第i件物品后未满,则继续选取第i+1件, 若该件物品“太大”不能装入,则弃之,继续选取下一件,直至背包装满为止。 如果在剩余的物品中找不到合适的物品以填满背包,则说明“刚刚”装入的物品 “不合适”,应将它取出“弃之一边”,继续再从“它之后”的物品中选取,如此 重复,直到求得满足条件的解,或者无解。 由于回溯求解的规则是“后进先出”,自然要用到“栈”。3.进一步考虑: 如果每件物品都有体积和价值,背包又有大小限制,求解背包中存放物 品总价值最大的问题解---最优解或近似最优解。

*/#include <stdio.h>

#include <stdlib.h>

struct node{

int sum;

int i;

};

typedef struct node NODE;

int getmemory(int **p,int size)

{

if(0 >= size) return NULL;

if(NULL == (*p=(int *)malloc(size * (sizeof(int)))))

return 0;

else

return 1;

}

int assignvalue( int *dest,int size)

{ if(NULL==dest)

return 0;

while(size>0)

{

scanf("%d",dest);

dest++;

size--;

}

return 1;

}

int solution(int *source,int volume, int size)

{

int i, j;

//j用来存储相对栈首地址的便宜量 int *stack;

//申请的栈空间 int *header;

NODE temp;

if(NULL==source || 0==volume || 0==size) return 0; if(NULL==(stack=(int *)malloc(size*sizeof(int))))

return 0;

header=stack;

for(i=0;i<size;i++)

{

stack=header;

//每一次循环都使栈回到首地址 j=0;

//每一次循环都使栈的空间使用率为0;

temp.i=temp.sum=0;

//每一次循环都将使和以及空间计数值变为0;

//每次运算需要计算的次数, 第一次循环需要对size个值进行检验

//第二次循环则需要对size-i个值进行检验

while(temp.i <= size-i)

{

j++;

temp.sum += *(source+i+temp.i);

*stack=*(source+i+temp.i);

stack++;

if(temp.sum==volume)

//当求出来的和与容积大小相等时就输出

{

while(j>0)

{

printf("%d ",*(stack-1));

j--;

stack--;

}

putchar(&#39;\n&#39;);

//输出完毕就跳出循环,继续对下一轮的数据进行求和

}

if(temp.sum < volume)

//如果取出的值加上后小于容积,则继续取下一个值进行运算

{

temp.i++;

continue;

}

if(temp.sum > volume)

//如果取出来的值加上大于容积,则丢弃,同时将刚压栈的数据出栈

{

temp.sum -= *(source+i+temp.i);

temp.i++;

*stack=0;

j--;

stack--;

continue;

}//end of if

}//end of while

}//end of for

free(stack);

free(header);

return 1;

}

int main(int argc, char *argv[]){

int size;

int volume;

int *number;

number=NULL;

printf("input the total number of the package:");

scanf("%d",&size);

printf("\nEnter the elements in the package:\n"); if(!getmemory(&number,size)) exit(1);

if(!assignvalue(number,size)) exit(1);

puts("\nPlease enter the volum of the package:");

scanf("%d",&volume);

if(0==solution(number,volume,size))

exit(1);

return 0;

}

现在的代码还没有考虑输入、输出的排版问题,等整个问题解决的时候再说吧...........

我发现有时候C语言还真有意思, 很容易实现一些有意思的问题。

上面的代码还没有完成,只是出具模型了, 以后慢慢弄点关于数据结构的命题来讨论讨论。

欢迎各位大侠弯腰找板砖............

相关文章
最新文章
热点推荐