knapsock.cpp

01背包问题演示程序 用mfc实现01背包问题的dp算法

// KnapSock.cpp: implementation of the KnapSock class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "01knapsackMFC.h"
#include "KnapSock.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

KnapSock::KnapSock()
{
	value = NULL;
	weight = NULL;
	vmax = NULL;
	num = 0;
	max = 0;
	flag = 0;
}

KnapSock::~KnapSock()
{
	//delete []value;
	//delete []weight;
	for (int i = 0; i <= num; i++)
	{
		delete []vmax[i];
	}
	delete []vmax;
}

KnapSock::KnapSock(int n, int m, int* w, int* v)
{
	num = n;
	max = m;
	//value = new int[n];
	//weight = new int[n];
	value  = v;
	weight = w;
	vmax = new int*[n+1];
	for (int i = 0; i <= n; i++)
	{
		vmax[i] = new int[m+1];
	}
	flag = 0;
}

void KnapSock::FindWay()
{
	if (flag == 1)
	{
		return;
	}
	for (int i = 0; i <= num; i++)
	{
		vmax[i][0] = 0;
	}
	for (int j = 1; j <= max; j++)
	{
		vmax[0][j] = 0;
	}
	for ( i = 1; i <= num; i++)
	{
		for ( j = 1; j <=max; j++)
		{
			if ((j < weight[i]) || (vmax[i-1][j] >= vmax[i-1][j-weight[i]] + value[i]))
			{
				vmax[i][j] = vmax[i-1][j];
			}
			else
			{
				vmax[i][j] = vmax[i-1][j-weight[i]] + value[i];
			}
		}
	}
	flag = 1;
}

BOOL KnapSock::Mark(int *obj)
{
	if (flag == 0)
	{
		return FALSE;
	}
	weightgot = 0;
	int j = max;
	for (int i = num; i > 0; i--)
	{
		if (!(vmax[i][j] == vmax[i-1][j]))
		{
			obj[i] = 1;
			j -= weight[i];
			weightgot += weight[i];
		}
		else
		{
			obj[i] = 0;
		}
	}
	return TRUE;
}

int KnapSock::ValueGot()
{
	if (flag == 0)
	{
		return -1;
	}
	return vmax[num][max];
}

int KnapSock::WeightGot()
{
	if (flag == 0)
	{
		return FALSE;
	}
	return weightgot;
}