新建 文本文档.txt

数据结构算法背包问题解法之递归解法

*
*背包问题之递归解法
*code CG
*2008 12 30
*/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
#define N 5 /*控制输入的元素的个数*/
#define MAX 100 /*背包最大可放重量*/
int result;
int select[N],selectW[N];
struct{
  int weight;
  int price;
}items[N];  /*定义物件结构体*/
/*
*knapsacks()背包递归算法
*参数：int i 要放入的物件游标位置
	   int w 已用背包重量
	   int p 可使用的最大价格
*/
void knapsacks(int i, int w, int p){/*背包递归算法*/
  int k;
  if ((w + items[i].weight) < = MAX){ /*物品I重量放入背包是否满足*/
	selectW[i] = 1;			 /*重量满足，暂时放入背包*/
	if (i < N - 1){/*i < N-1?*/
	  knapsacks(i + 1, w + items[i].weight, p);
	  }
	else{
	  for (k = 0; k < N ; k++){
		  select[k] = selectW[k];/*selectW -> select*/
		  }/*for*/
	  result = p;
	  }/*else*/
	}/*if*/
	if (p - items[i].price > result){/*如果物品i不放入背包的情况，还原 */
	  selectW[i] = 0;
	  if (i < N - 1){
		 knapsacks(i + 1, w ,p - items[i].price);
		 }
	  else{
		   for(k = 0; k < N; k++){/*selectW -> select*/
		   select[k] = selectW[k];
		   }
	   result = p - items[i].price;
	   }/*else*/
  }/*if*/
}/*knapsacks*/
int main(){
int i;
int w = 0,v = 0;
int sumPrice = 0;			/*输入计数器*/
int maxWeight = MAX;
printf("input W and V :w,v\n");
for (i = 0; i < N ; i++){
	scanf("%d,%d",&w,&v);
	items[i].weight = w;
	items[i].price = v;
	printf("W = %d,P = %d\n",items[i].weight, items[i].price);
	selectW[i] = 0;  /*清空记录数组*/
	select[i] = 0;
	sumPrice += v;  /*记录总价格数据*/
}/*for*/
printf("Max Weight:%d\n", maxWeight);
result = 0;
printf("sumPrice:%d\n", sumPrice);
knapsacks(0, 0, sumPrice);/*开始背包操作*/
printf("| ID | WT | PR |\n");
for (i = 0; i < N; i++){
	if (select[i]){
		   printf("|%-4d|%-4d|%-4d|\n",i+1,items[i].weight, items[i].price);
	   }
}/*for*/
printf("Result:%d\n", result);
system("PAUSE");
return 0;
}