今天讲点简单的算法，最简单的背包 0 算法，使用了递归的方法，相信看完代码的朋友会发现这段代码很熟悉，不过 CG 提供这些代码的目的只是让全部背包算法的完整提供地给大家，代码很简单，相信高手一看就懂，这里的背包算法只是考虑了物品的重量，没有考虑物品的价值，是初学递归算法的朋友必看的代码，高手的话全当复习一下吧。 因为 CG 最近要考试了，一口气要考 6 门，所以博客更新没有这么快了，请大家见谅不过我还是会保持每天提供至少一篇的速度写博文，希望大家能支持，谢谢 预告下明天的算法博文，《银行家算法》，今天复习了下操作系统，晚上重新安装了系统，浪费了两个小时，代码明天调试后奉上，希望大家继续关注。
/* 简单的背包问题递归解
*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*/