knapsack.cpp

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

#include <stdio.h>
#include <stdlib.h>
#include "knapsack.h"

void KnapsackByExhaustion(int i)
{
	if(i>MAXSIZE)
	{
		if(CurrentValue>BestValue)
		{
			BestValue = CurrentValue;
			for(int k=1; k<=MAXSIZE; k++)
				Xi[k] = CurrentXi[k];
		}
		return;
	}

	for(int j=0; j<=1; j++)
	{
		if((CurrentWeight+knapsack.Weight[i])<=CAPACITY && j==1)
		{
			CurrentXi[i]=1;
			CurrentWeight+=knapsack.Weight[i];
			CurrentValue+=knapsack.Value[i];
			KnapsackByExhaustion(i+1);
			CurrentWeight-=knapsack.Weight[i];
			CurrentValue-=knapsack.Value[i];
		}
		else
			KnapsackByExhaustion(i+1);

	}
}

void InitKnapsack()
{
	FILE *fp;
	ITEM item;
	fp=fopen("items.txt", "rb");
	for(int i=1; i<=MAXSIZE; i++)
	{
		fread(&item, sizeof(item), 1, fp);
		knapsack.Weight[i]=item.weight;
		knapsack.Value[i]=item.value;
	}
	knapsack.Capacity=CAPACITY;
}

void PrintKnapsackInfo()
{
	PrintTitle("背包的信息为");
	printf("重量：\t");
	for(int i=1; i<=MAXSIZE; i++)
		printf("%d\t", knapsack.Weight[i]);
	printf("\n价值：\t");
	for(i=1; i<=MAXSIZE; i++)
		printf("%d\t", knapsack.Value[i]);
	printf("\n背包的容量是：%d\n", knapsack.Capacity);
}

void PrintSelect()
{
	PrintTitle("当前背包的最优解");
	printf("产生的最大价值:%d\t\n", BestValue);
	printf("选择物品的组合:\t");
	for(int i=1; i<=MAXSIZE; i++)
	{
		if(Xi[i] == 1)
			printf("%d\t", i);
	}
	printf("\n\n");
	system("pause");
}

void PrintTitle(char * prmTitle)
{
	for(int i=1; i<20; i++)
		printf("-");
	printf("%s", prmTitle);
	for(i=1; i<20; i++)
		printf("-");
	printf("\n");
}