#include<stdio.h>

#define NUM 10/* 定義物品總數*/
#define CONTENT 10 /*定義包的容量*/
void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT])
{
    int n=NUM-1;
    int i,j;
    int jMax;
    if((w[n]-1)< c)
	jMax = w[n]-1;
    else
	jMax = c;
    /* 初始化m[n][j] */
    for(j = 0; j <= jMax; j++)
	m[n][j] = 0; 
    for(j = jMax +1; j <= c; j++)
	m[n][j] = v[n]; 
   /*使用非遞歸的算法來求解m[i][j] */
   for(i = n-1; i > 0; i--)
   {
   	 if((w[i]-1)< c)
	    jMax = w[i]-1;
        else
	    jMax = c;
        for(j = 0; j <= jMax; j++)
	    m[i][j] = m[i+1][j] ; 
        for(j = jMax +1; j <= c; j++)
        {
            if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i]))
	        m[i][j] = m[i+1][j] ; 
	    else
		m[i][j] = 	m[i+1][j-w[i]]+v[i];
	}
   }
   if(c>w[0])
   {
	   if(m[1][c] >= (m[1][c-w[0]]+v[0]))
	   	 m[0][c]= m[1][c]; 
	   else
		m[0][c]= m[1][c-w[0]]+v[0]; 
   }
   else
   	m[0][c]= m[1][c];
	
}
/*尋找最優解*/
void traceback(int flag[NUM],int w[NUM],int m[NUM][CONTENT])
{
	int n = NUM -1;
	int i;
	int c = CONTENT;
	for(i = 0; i < n; i++)
	{
		if(m[i][c] == m[i+1][c])
			flag[i] = 0;
		else
		{
			flag[i] = 1;
			c-=w[i];
		}
	}
	if(m[n][c] >0)
	    flag[n] = 1;
	else
	    flag[n] = 0;
}
/* 打印最優解*/
void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT])
{
	int i;
	printf("the knapsack should contain:\n");
	printf(" num weight value \n");
	for(i = 0;i < NUM; i++)
	{
		if(flag[i] == 1)
	            printf("  %d    %d     %d\n",i,w[i],v[i]);
	}
	printf("the max value in the knapsack is: %d\n",m[0][CONTENT]);
}
int main()
{
	int value[NUM]={5,2,3,4,3,6,5,7,8,2};
	int weight[NUM]={2,1,3,2,4,3,5,6,2,2};
	int c = CONTENT;
	int maxvalue[NUM][CONTENT];
	int flag[NUM]={0,0,0,0,0,0,0,0,0,0};
	clrscr();
	printf("****************************************\n");
        printf("*      this program will solve         *\n");
        printf("*    the problem of 0-1knapsack        *\n");
        printf("****************************************\n");
	/*計算最優值*/
	knapsack(value,weight,c,maxvalue);
	/*構造最優解*/
	traceback(flag,weight,maxvalue);
	/*打印程序的結果*/
	printResult(flag,weight,value,maxvalue);
	getch();
	return 0;	
}