背包问题递归.c

C语言常用算法 之 背包问题 常用代码 方便使用

#include<stdio.h>
#define N 7
#define S 15

int w[N+1]={0,1,4,3,4,5,2,7};

int knap(int s, int n)
{
     if (s==0) return 1;
	 if(s<0||(s>0&&n<1)) return 0;
	 if (knap(s-w[n],n-1) )
	 {
		 printf("%4d",w[n]);
		 return 1;
	 }
     return  knap(s,n-1)  ;
}

void main()
{
	if(knap(S,N)) printf("OK!\n");
	else printf("NO!\n");
}