设有个背包，它能放的重量为S，设有N件物品，其重量分别为w1，w2，...，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。可以用递归解决的基础是每次选择一个物品放入背包，那么剩余物品和背包剩余数量又构成一个新的背包问题。
#include<stdio.h> /**//*N定义为7，即有7件物品；S定义为15，即背包能放的重量为15，比如15公斤*/
#define N 7
#define S 15
int w[N+1] = 
{0,1,4,3,4,5,2,7}; /**//*给定各物品的重量值，放入数组w[N+1]中*/
int knap(int s,int n) /**//*knap函数递归计算出符合选择要求的物品，并显示其重量。形参s 实际是放入物品i后，背包还能装载的重量，n为考查物品i后下一个待考查的物品。*/
{ if(s == 0) return 1; /**//*如果s等于0时返回0并退出knap函数 */
if ( s<0|| ( s>0 && n<1 )) return 0; /**//*如果s<0或s>0同时n<1则返回0*/
if (knap(s-w[n],n-1)) /**//*考查物品n被选择的情况*/
{
printf("%d ",w[n]); /**//*在屏幕上打印被选择的物品的重量*/
return 1; /**//*返回1*/
}
return knap(s,n-1); /**//*考查不选择物品n的情况*/
}
main() {
if (knap(S,N)) printf( " OK! " ); /**//*如果knap最终返回1，打印OK!则表示成功选出一组物品*/
else printf( "N0! " ); /**//*否则打印NO！表示没有选出合适的一组!*/
}
用代码中的数据结果为：
1 5 2 7
OK！
如果物品用这一组0,1,1,3,1,5,2,1 就会是NO！
posted on 2005-02-26 19:16 小刀人 阅读(5264)
评论(3) 编辑 收藏