李大仁博客

/*简单的背包问题递归解
*code CG 2009-01-04
*/
#include"stdio.h"
#define N 6 /*物品数量*/
#define S 15 /*背包大小*/
 
int W[N+1]={0,1,2,3,4,5,6};/*测试数据，各物品重量，W[0]不使用*/
 
/*knapsack()背包函数
参数	int s 剩余重量
		int n 剩余物品数
返回	int 背包分配是否成功
*/
int knapsack(int s,int n){
	if(s == 0)/*分配结束，成功*/
		return 1;
	if(s < 0 || (s > 0 && n < 1))/*没有可用空间，或者物品分配完毕*/
		return 0;
	if( knapsack(s - W[n] , n - 1)){/*递归*/
		printf("%-4d",W[n]);	/*输出*/
		return 1;
	}
return knapsack(s , n - 1);
}
int main()
{
	if(knapsack(S , N))/*递归调用*/
		printf("nOK!n");
	else
		printf("Failed!");
	return 1;
}/*main*/