knapsack.h

0/1背包问题的几种解法

#define MAXSIZE 26
#define CAPACITY 500

static int Xi[MAXSIZE+1];
static int CurrentXi[MAXSIZE+1];
static int CurrentWeight=0;
static int CurrentValue=0;
static int BestValue=0;

static int Value[MAXSIZE+1];
static int Weight[MAXSIZE+1];

typedef struct
{
	int Value[MAXSIZE+1];
	int Weight[MAXSIZE+1];
	int Capacity;
}KNAPSACK;

typedef struct
{
	int id;
	double ValuePerUnit;
}UNITVALUE;
static UNITVALUE ValuePerUnit[MAXSIZE+1];

typedef struct{
	int weight;
	int value;
}ITEM;

void KnapsackByTrackback(KNAPSACK prmKnapsack);
void Backtrack(int i);
int Bound(int i);

void InitKnapsack(KNAPSACK * prmKnapsack);
void PrintKnapsackInfo(KNAPSACK prmKnapsack);
void PrintSortedItems();
void PrintSelect();
void PrintTitle(char *);

void QuickSort(UNITVALUE *prmValuePerUnit, int low, int high);
int Partion (UNITVALUE *UnitValueList, int low, int high);