// 背包問題.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];  //定義一個數(shù)組作為棧用
    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--;         //兩次出棧,繼續(xù)查找滿足條件的解
		  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("輸入物品的件數(shù)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);
}