背包.cpp

这是一个“背包”问题的数据结构的Ｃ语言实现。我个人觉得是考查对链表和二叉树的知识。去年学的是这个

#include<stdio.h>

int S,log,m=0;
typedef struct 
{
	int add;
	int weight;
	int last;
}result;

result  bag[2000];

result  temp;

void  push(int a,int b)
{
	temp.weight=a+b;
}

void init()
{
	bag[0].weight=0;
	bag[0].last=0;
	bag[0].add=0;
}

void printpath(int length)  //输出路径

{    
       if(length>0)

       { 
        log=bag[length].last;
      
        printpath(log); 
		if(bag[bag[length].last].add!=0)
		printf("%d  ",bag[bag[length].last].add);  

       }     
}




void f1(int n,int W[])
{   int j;
	int father=0;
	int length=0;
    long  s=0;
    while(s<=n*n*n)
	{
	   
	       for(j=1;j<=n;j++)   //第i个数可以和n-i个数(排在后面的数)相加，产生新的结果　
		   { 
			   if(W[j]>bag[father].add)
			   {
			      temp=bag[father];
                  bag[++length].add=W[j];
                  push(temp.weight,bag[length].add);

			      bag[length].weight=temp.weight;
			      bag[length].last=father;



                  if(bag[length].weight==S)
				  {  
					  if(m==0)printf("可以有以下的方案\n");  

				      length++;  
                      bag[length].last=length-1;
                      printpath(length);  
					  m=1;
				      printf("\n");
					  length--;
				  } 
			   }

		   }
		   s=s+n;
		   father++;
	 
	}
	
	if (m==0) printf("不能把包装满!\n");
}




void main()
{
int n,i;
int W[100];

bag[0].weight=0;

printf("背包的容量S:");

scanf("%d",&S);

printf("物品的个数n:");
scanf("%d",&n);


printf("请输入每个物品的重量");
 for(i=1;i<=n;i++)
	scanf("%d",&W[i]);

init();
f1(n,W);


}