设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w[1], w[2], …, w[n]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。
/*
背包问题
*/
#include<stdio.h>
#include<malloc.h>

#define TRUE 1
#define FALSE 0

typedef unsigned char BOOL;

/*物品装入状态表和重量表的头指针*/
BOOL * ifexist=NULL;
float * weight=NULL;
unsigned int cargo_num;/*物品的数量*/
float capacity;/*背包容量*/

void outstatus(BOOL * tStat, unsigned int num)
{
unsigned int i;
printf("SOLVE:{");
for(i=1;i<=num;i++)
{
if(tStat[i]==TRUE)
printf("[%d(Wt:%.2f)]",i,weight[i]);
}
printf("}\n");
}

/*
递归搜索：

若s=0, 有解；若s<0, 无解；
若s>0, 但n<1(就是说已经没有物品可以尝试), 无解；
否则：（也即是s>0且n>=1）

若选择当前物品，将 knap(s-w[n],n-1)的结果作为结果；
若不选择当前物品，将 knap(s,n-1)的结果作为结果；
*/
BOOL knap(float cWeight, unsigned int n)
{
BOOL retbuf;
BOOL retvalue;

if(cWeight==0)
{
outstatus(ifexist, capacity);
return TRUE;
}
if(cWeight<0)
{
return FALSE;
}
/*若CWEIGHT>0(隐含)但…*/
if(n<1)
{
return FALSE;
}

ifexist[n]=FALSE;
retvalue = knap(cWeight,n-1);

ifexist[n]=TRUE;
retbuf = knap(cWeight-weight[n], n-1);
if(retbuf==TRUE) retvalue=TRUE;
ifexist[n]=FALSE;

return retvalue;
}

void main(void)
{

unsigned int i;

BOOL success_flag=FALSE;

/*输入货物数量*/
fflush(stdin);
printf("Give the number of the cargos:");
scanf("%d",&cargo_num);
/*输入背包容量*/
fflush(stdin);
printf("Give the capacity of the package:");
scanf("%f",&capacity);

/*给表格分配空间*/
ifexist = (BOOL *)malloc(sizeof(BOOL)*(cargo_num+1));
weight = (float *)malloc(sizeof(float)*(cargo_num+1));
/*输入各个重量*/
for(i=1;i<=cargo_num;i++)
{
ifexist[i]=FALSE;
printf("Weight[%d]:",i);
fflush(stdin);
scanf("%f",&weight[i]);
}

success_flag=knap(capacity, cargo_num);


if(success_flag==TRUE)
{
printf("There's solution(s) for this problem.\n");
}
else
{
printf("There's no solution for this problem.\n");
}

free(ifexist);
free(weight);
getch();
}