理解动态规划——01背包问题

2019-11-08 02:14:50

字体：大中小

来源：转载

供稿：网友

1. 概述

01背包问题是很经典的动态规划问题。它的核心便是一个最大化公式

其中f(i, j)前面i个商品在背包容量为j的情况下达到的最大的价值；weight[i]是第i件商品的重量；PRize[i]是商品的价值。也就是在现在这个背包大小情况下在选择还是不选择当前商品中求取总价值最大化。本文中使用较为经典的方式（使用中间表）来解决该问题。这是本文中测试数据得到的中间表：

该表的创建顺序是：从上往下，从左往右创建的。表中0~10的数字代表的是背包的容量，背包容量在增长的过程中，最大化背包中商品的价值。举个栗子：表中价格为3，大小为2开始表格往上生长；直到遇到商品大小为2，价值为6的商品时经过最大化比较背包中九堡原来的商品换成了价值为6，大小为2的商品了。后面的情况也是一次类推的。在实现了中间表的创建之后，接下来的工作就是要寻找到撞到背包中的商品了，寻找商品的过程也是通过这张表来实现的。

在寻找背包中商品的过程中，首先从表的右上角开始寻找（因为那个地方的价值是最大的）。开始设置背包的容量是满额的（即为10），减去上面红色标记15对应商品的价值（即为6），且因为最大价值哪行商品已经被统计了，因而开始向下走则就找到上表中红色标记为9的上方那块位置，其中也满足条件两个位置之间的价值差是选择了的商品的价值。因而价值为6大小为4的商品被选中。接下来寻找第二个商品，由于原本寻找到的第二个商品（红色标记为9上方那个商品）对应的背包余量减去改行商品的大小后，简直不能满足，因而往下移一行。大体的流程是这样的。为本表述恐有不明了之处，请查看代码和推敲很快便能得出其缘由。

2. 实现

//构造函数1CPackage01_Problem::CPackage01_Problem(){	this->m_ItemCount = 5;	unsigned int price[] = {3, 4, 6, 5, 6};	unsigned int size[] = {2, 5, 2, 6, 4};	this->m_pItemPrice = new unsigned int[this->m_ItemCount];	this->m_pItemSize = new unsigned int[this->m_ItemCount];	for (unsigned int i=0; i<this->m_ItemCount; i++)	{		this->m_pItemPrice[i] = price[i];		this->m_pItemSize[i] = size[i];	}	this->m_PackageSize = 10;}//构造函数2CPackage01_Problem::CPackage01_Problem(unsigned int* ItemPrice, unsigned int ItemCount, unsigned int* ItemSize, unsigned int PackageSize){}CPackage01_Problem::~CPackage01_Problem(){	if (nullptr != this->m_pItemPrice)	{		delete[] this->m_pItemPrice;		this->m_pItemPrice = nullptr;	}	if (nullptr != this->m_pItemSize)	{		delete[] this->m_pItemSize;		this->m_pItemSize = nullptr;	}}unsigned int CPackage01_Problem::Get01_Result(){	unsigned int* m_PackageMatrix = new unsigned int[this->m_ItemCount*(this->m_PackageSize+1)];	//定义	memset(m_PackageMatrix, 0, sizeof(unsigned int)*this->m_ItemCount*(this->m_PackageSize+1));	//清零	unsigned int m_cols = this->m_PackageSize+1;	for (unsigned int i=1; i<=this->m_PackageSize; i++)	{		for (unsigned int j=0; j<this->m_ItemCount; j++)		{			if (i < this->m_pItemSize[j])			{				if (0 == j)				{					m_PackageMatrix[j*(this->m_PackageSize+1) + i] = 0;				}				else				{					m_PackageMatrix[j*m_cols + i] = m_PackageMatrix[(j-1)*m_cols + i];				}			}	//背包太小了装不下该商品			else			{				unsigned int temp_value(0);				if (0 == j)				{					m_PackageMatrix[j*m_cols + i] = this->m_pItemPrice[j];					continue;				}	//第一个商品可以放入背包,之前背包中没有东西先放进去再说，不是价值最大的就回溯				else				{					temp_value = m_PackageMatrix[(j - 1)*m_cols + i - this->m_pItemSize[j]] + this->m_pItemPrice[j];				}				m_PackageMatrix[j*m_cols + i] = temp_value > m_PackageMatrix[(j-1)*m_cols + i] ? temp_value : 					m_PackageMatrix[(j-1)*m_cols + i];			}	//背包的容量可以装下该商品了，		}	//选区的商品变化	}	//背包容量变化	for (unsigned int i = 0; i < this->m_ItemCount; i++)	{		for (unsigned int j = 0; j <= this->m_PackageSize; j++)		{			std::cout << m_PackageMatrix[i*m_cols + j] <<"  ";		}		std::cout << std::endl;	}	//打印中间矩阵	//寻找背包问题的解	unsigned int packagesize = this->m_PackageSize;	//获取背包的体积	cout << "/t价格" << "/t大小" << endl;	for (unsigned int i=this->m_ItemCount-1; i>=0; i--)	{		if (packagesize == 0)		{			break;		}	//余量为0了退出		if (i == 0 && packagesize > 0)		{			cout << "/t" << this->m_pItemPrice[i] << "/t" << this->m_pItemSize[i] << endl;			break;		}	//找到了最后一个商品但是还有余量 则添加进结果		unsigned pos = (packagesize -this->m_pItemSize[i]) < 0? 0:(packagesize -this->m_pItemSize[i]);	//防止寻址越界		if (m_PackageMatrix[i*m_cols + packagesize] - m_PackageMatrix[(i-1)*m_cols + pos] == this->m_pItemPrice[i])		{			cout << "/t" << this->m_pItemPrice[i] << "/t" << this->m_pItemSize[i] << endl;			packagesize -= this->m_pItemSize[i];		}	//当前商品对应重量余量 减去 该商品的上一个商品对应背包容量（当前容量减去当前商品大小）			//对应的价格等于现在商品的价格时既是需要寻找的商品	}	delete[] m_PackageMatrix;	m_PackageMatrix = nullptr;	return 0;}#pragma once//O1背包问题class CPackage01_Problem{public:	CPackage01_Problem();	CPackage01_Problem(unsigned int* ItemPrice, unsigned int ItemCount, unsigned int* ItemSize, unsigned int PackageSize);	~CPackage01_Problem();private:	unsigned int* m_pItemPrice;			//商品的单价数组	unsigned int* m_pItemSize;			//商品的重量	unsigned int m_ItemCount;			//商品的总数目	unsigned int m_PackageSize;			//背包的大小public:	unsigned int Get01_Result();};3. 结果