knapsack.cpp

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

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

void KnapsackByDp(int prmValue[], int prmWeight[], int prmCapacity, int (*prmBestValue)[CAPACITY+1])
{
	for(int j=0; j<=prmCapacity; j++)
		prmBestValue[0][j] = 0;

	int jMax;
	for(int i=1; i<=MAXSIZE; i++)
	{
		jMax = Min(prmWeight[i],prmCapacity);
		for(j=0; j<jMax; j++)
			prmBestValue[i][j] = prmBestValue[i-1][j];
		for(j=prmWeight[i]; j<=prmCapacity; j++)
			prmBestValue[i][j] = Max(prmBestValue[i-1][j], prmValue[i] + prmBestValue[i-1][j-prmWeight[i]]);
	}
	PrintTitle("当前背包的最优解");
	printf("产生的最大价值是：%d\t\n",prmBestValue[MAXSIZE][CAPACITY]);
}

void TraceBack(int (*prmBestValue)[CAPACITY+1], int prmWeight[], int prmCapacity)
{
	for(int i=MAXSIZE; i>=1; i--)
		if(prmBestValue[i][prmCapacity] == prmBestValue[i-1][prmCapacity])
			Xi[i] = 0;
		else
		{
			Xi[i] = 1;
			prmCapacity -= prmWeight[i];
		}
}

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()
{
	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");
}

int Min(int prmA, int prmB)
{
	if(prmA>prmB)
		return prmB;
	else
		return prmA;
}

int Max(int prmA, int prmB)
{
	if(prmA>prmB)
		return prmA;
	else
		return prmB;
}