背包问题.cpp

数据结构的课程设计

// 背包问题.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>
#include<malloc.h>
#define maxsize 100
void fun(int r[],int n,int v)     //求解
{
   int s[maxsize];  //定义一个数组作为栈用
    int y,i,j,k,p,t=0;
 while(t<n)
 {
    j=t++;
	y=0;
	i=0;
	while(j<n)
	{
      while(j<n&&y<v)
	  {
		s[i]=j;
		y=y+r[j];
		i++;
		j++;
	  }
    	if(y==v)
		{
          printf("\n");     //顺序输出满足条件的物品的体积
		  for(p=0;p<i;p++)
           printf("%d ",r[s[p]]);
		  i--;         //两次出栈,继续查找满足条件的解
		  y=y-r[s[i]];
          i--;
		  y=y-r[s[i]];
		  j=s[i]+1;
			  
		}
    	else if(y>v&&i>0)
		  { k=j;
            y=y-r[--k];
            i--;
		  }
		if(j>=n&&i>0)       //若查找完一次但没有符合条件的解，将前一个出栈重新找
		{   i--;
	    	j=s[i]+1;
			y=y-r[i];
		}
	}
 }
}
void main()
{
int *r,i,n,v;
printf("输入物品的件数n和背包所能装入的总体积v\n");
scanf("%d%d",&n,&v);
r=(int*)malloc(n*sizeof(int));
printf("输入各件物品的体积\n");
for(i=0;i<n;i++)
scanf("%d",&r[i]);
printf("满足条件的解有：");
fun(r,n,v);
}