李大仁博客

/*
*背包问题之递归解法
*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,vn");
for (i = 0; i < N ; i++){
    scanf("%d,%d",&w,&v);
    items[i].weight = w;
    items[i].price = v;
    printf("W = %d,P = %dn",items[i].weight, items[i].price);
    selectW[i] = 0;  /*清空记录数组*/
    select[i] = 0;
    sumPrice += v;  /*记录总价格数据*/
}/*for*/
printf("Max Weight:%dn", maxWeight);
result = 0;
printf("sumPrice:%dn", 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:%dn", result);
system("PAUSE");
return 0;
}