knapsack.cpp

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

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

void KnapsackByTrackback(KNAPSACK prmKnapsack)
{
	for(int i=1; i<=MAXSIZE; i++)
	{
		ValuePerUnit[i].id=i;
		ValuePerUnit[i].ValuePerUnit = (double)prmKnapsack.Value[i]/prmKnapsack.Weight[i];
	}
	QuickSort(ValuePerUnit, 1, MAXSIZE);

	for(i=1; i<=MAXSIZE; i++)
	{
		Value[i]=prmKnapsack.Value[ValuePerUnit[MAXSIZE-i+1].id];
		Weight[i]=prmKnapsack.Weight[ValuePerUnit[MAXSIZE-i+1].id];
	}
	PrintSortedItems();
	Backtrack(1);
}

void PrintSortedItems()
{
	PrintTitle("物品按单位价值从大到小顺序排列为");
	for(int i=1; i<=MAXSIZE; i++)
	{
		printf("%d\t", Weight[i]);
	}
	printf("\n");
	for(i=1; i<=MAXSIZE; i++)
	{
		printf("%d\t", Value[i]);
	}
	printf("\n");
}

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


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

	if(CurrentWeight+Weight[i]<=CAPACITY)
	{
		CurrentXi[i] = 1;
		CurrentWeight+=Weight[i];
		CurrentValue+=Value[i];
		Backtrack(i+1);
		CurrentWeight-=Weight[i];
		CurrentValue-=Value[i];
	}
	if(Bound(i+1)>BestValue)
	{
		CurrentXi[i]=0;
		Backtrack(i+1);
	}
}

int Bound(int i)
{
	int remnant = CAPACITY-CurrentWeight;
	int bound = CurrentValue;

	while(i<=MAXSIZE&&Weight[i]<=remnant)
	{
		remnant-=Weight[i];
		bound+=Value[i];
		i++;
	}

	if(i<=MAXSIZE)
		bound+=Value[i]/Weight[i]*remnant;
	return bound;
}

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

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

void PrintSelect()
{
	PrintTitle("当前背包的最优解");
	printf("获得的最大价值是：%d\n", BestValue);
	printf("选择物品的组合是：\t");
	for(int i=1; i<=MAXSIZE; i++)
	{
		if(Xi[i]==1)
			printf("%d\t", ValuePerUnit[MAXSIZE-i+1].id);
	}
	printf("号物品。\n\n");
	system("pause");
}

int Partion (UNITVALUE *UnitValueList, int low, int high)
{
	UnitValueList[0]=UnitValueList[low];
	double pivotkey=UnitValueList[low].ValuePerUnit;
	while (low<high)
	{
		while(low<high && UnitValueList[high].ValuePerUnit>=pivotkey)
			--high;
		UnitValueList[low]=UnitValueList[high];
		while(low<high && UnitValueList[low].ValuePerUnit<=pivotkey)
			++low;
		UnitValueList[high]=UnitValueList[low];
	}
	UnitValueList[low]=UnitValueList[0];
	return low;
}

void QuickSort(UNITVALUE *UnitValueList, int low, int high)
{
	if(low < high)
	{
		int pivotloc=Partion(UnitValueList,low,high);
	    QuickSort(UnitValueList,low,pivotloc-1);
		QuickSort(UnitValueList,pivotloc+1,high);
	}
}