#include<stdio.h>
bool Done;
int next;
void parts(int P[],int W[],int F[],int x[],int p[],int w[],int n);
int DKNAP(int P[],int W[],int n,int M,int p[],int w[],int x[]);

int DKNAP(int P[],int W[],int n,int M,int p[],int w[],int x[])
{
	int F[128];
	int pp,ww,l,h,u ,i,j,k,r;
	F[0]=1;
	P[1]=W[1]=0;                            //S0//
	l=h=1;                                  //S0的首端與末端//
	F[1]=next=2;                            //P和W中第一個空位//
	for(i=1;i<=n;i++)
	{
		k=r=l;
		Done=false;
		while(r<=h&&!Done)
		{
			if(W[r]+w[i]<=M)                //u為1<=r<=h中使得W[r]+w[i]<=M的最大的r//
			{
				u=r;
				r++;
			}
			else Done=true;
		}
		for(j=l;j<=u;j++)                   //生成S1i及歸并//
		{
			pp=P[j]+p[i];
			ww=W[j]+w[i];                   //S1i中的下一個元素//
			while(k<=h&&W[k]<ww)            //從S(i-1)中取元素來歸并,S(i-1)中W[k]比ww小的可以直接加入Si//
			{
				P[next]=P[k];
				W[next]=W[k];
				next++;
				k++;
			}
			if(k<=h&&W[k]==ww)              //相等則較大效益值賦值給pp//
			{
				pp=(pp>=P[k])?pp:P[k];
				k++;
			}
			if(pp>P[next-1])                
			{
				P[next]=pp;
				W[next]=ww;
				next++;
			}
			while(k<=h&&P[k]<=P[next-1]) k++;//清除//
		}                                                                                        
		while(k<=h)                          //將S(i-1)中剩余元素并入Si//
		{
			P[next]=P[k];                                      
			W[next]=W[k];                                                                                                                      
			next++;
			k++;
		}
		l=h+1;
		h=next-1;
		F[i+1]=next;
	}
	parts(P,W,F,x,p,w,n);
	return next;
}

void parts(int P[],int W[],int F[],int x[],int p[],int w[],int n)
{
	int a=next-1;
	int b,t,ppt,wwt;
	ppt=P[a];                              //將最末序偶(P,W)賦值給(ppt,wwt)將其初始化用于后來比較//
	wwt=W[a];
	for(b=n;b>=1;b--)                      //用回溯法求出背包問題的最優決策序列x[n]//
	{
		t=F[b-1];                          //t初值// 
		Done=false;                        //布爾變量Done用于控制內層循環
		while(t<F[b]&&!Done)
		{
			if(P[t]==ppt&&W[t]==wwt)       //在S(b-1)中找到(ppt,wwt)則取x(b)=0 
			{                              //否則置x(b)=1,并修改(ppt,wwt)
				x[b]=0;
				Done=true;
			}
			else t++;
		}
		if(t==F[b]) 
		{
			x[b]=1;
			ppt=ppt-p[b];
			wwt=wwt-w[b];
		}
	}
}

void main()
{
	int n,M,c,next=2;
	int P[256],W[256];
	int x[64],p[64],w[64];
	printf("*************算法4.7 0/1背包問題的算法實現*************\n"); 
	printf("請輸入物體的個數(1<=n<=64):");
	scanf("%d",&n);
	while(n<1||n>64)
	{
		printf("輸入有誤!!請重新輸入物體個數(1<=n<=64):");
		scanf("%d",&n);
	}
	printf("請輸入背包的容量M:");
	scanf("%d",&M);
	while(M<=0)
	{
		printf("輸入有誤!!請輸入一個正整數:");
		scanf("%d",&M);
	}
	printf("以下依次輸入物體的效益值和重量:)\n"); 
	for(c=1;c<=n;c++)
	{
		printf("p%d:",c);
		scanf("%d",&p[c]);
		printf("w%d:",c);
		scanf("%d",&w[c]);
		while(w[c]<0)
		{
			printf("輸入有誤!!請重新輸入一個正整數:");
			scanf("%d",&w[c]);
		}
		printf("\n");
	}
		next=DKNAP(P,W,n,M,p,w,x);
		printf("背包問題的最優解為:%d\n",P[next-1]);
		printf("相應的最優決策序列為:");
		for(c=1;c<=n;c++)
			printf("%-4d",x[c]);
}