C语言学习趣事_数据结构_经典命题_1_背包问题_分析_1
昨天测试了一下，如何通过函数从程序的堆栈空间来申请空间供其他函数使用， 里面提到了一个
数据结构的命题：背包问题。
命题如下：
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('\n');
//输出完毕就跳出循环，继续对下一轮的数据进行求和
}
if(temp.sum < volume)
//如果取出的值加上后小于容积，则继续取下一个值进行运算
{
temp.i++;
continue;
补充：软件开发 , C语言 ,
