0-1注解.txt

算法设计与分析：动态规划解决0-1背包问题

/**
* 程序名称：动态规划解0-1背包问题(C++语言版). 
*
* 说明:如果该程序进行了更新，可以在我的博客 http://yifanwq.itpub.net/  下载到最新的版本
*
* 该程序并非完全免费  对所有阅读该程序的用户实行 '良心付费 ' 的授权方法.
*       ①如果你认为该程序对你没用，或者你根本看不懂，请提出你的意见，联系QQ：442000868 
*       ②如果该程序对您理解 动态规划算法确实起来了一定的帮助作用，请作者美餐一顿吧！还是联系QQ：442000868 
*	             	┌───────────────────────┐
*                   │ 您的意见或您的美餐是作者最大的编程动力！！！ │
*					└───────────────────────┘
*/
#include <cstdlib>
#include <string>
#include <iostream>

//定义背包的容量
#define   C    9  

using namespace std;

//求最大值函数
int max(int x,int y)  
{
	return x >= y?x:y;
}

//求最小值函数
int min(int x,int y)
{
	return x>= y ? y:x;
}

/*求出背包解的备忘录矩阵
* v[] 价值数组
* w[] 物品的重量数组
* c   背包的容量
* n   物品的个数
* m   用于记录每步结果的备忘录矩阵(m是一个以物品的个数作为行数，
	  以总容量作为列数,例如有4个物品，背包的容量是10则该数组就应定义一个4行10列的数组，
	  但为了方便程序编写,常定义为5行11列的数组，第1行和第1列不用)
例如: w[]={0,7,4,6,2}  v[]={0,2,8,4,9}  c=C=9(开始的宏定义),n=4,则m(备忘录矩阵)是:
	┌─────────────────────┐
	│　│　│①│②│③│④│⑤│⑥│⑦│⑧│⑨│
	├─────────────────────┤
	│　│　│　│　│　│　│　│　│　│　│　│
	├─────────────────────┤
	│⑴│　│V │V │V │V │V │V │V │V │V │
	├─────────────────────┤
	│⑵│　│V │V │V │V │V │V │V │V │V │
	├─────────────────────┤
	│⑶│　│V │V │V │V │V │V │V │V │V │
	├─────────────────────┤
	│⑷│　│V │V │V │V │V │V │V │V │V │
	└─────────────────────┘
	行⑴…⑷代表可放入的物品为1…4
	列①…⑨背包的容量分别是1…9
	列代表矩阵中空格代表不会使用的区域(方便程序的理解)

   点(⑵,④)的V值可以这样理解:当背包的容量为4时，可选的物品有⑵,⑶,⑷里，背包的最优解.
   点(⑶,⑨)的V值可以这样理解:当背包的容量为9时，可选的物品有⑶,⑷里，背包的最优解.
   点(⑷,⑧)的V值可以这样理解:当背包的容量为8时，可选的物品只有⑷里，背包的最优解.

  在以下的程序解释中，如果矩阵中未写入具体的值，则代表该值还未进行计算.
*/

void Knaspack(int v[],int w[],int c,int n,int m[][C+1])   
{
	/**
	*----------------------------第一段(Begin)----------------------------------------------
	*该段代码主要填写备忘录矩阵的最后一行，因为前面几行的结果依耐于最后一行
	*该行分别记录当背包的容量分另为1,2…C(C是定义的背包容量)时，可选物品为第最后一个物品时的最优解
	*/

	/**
	*  为什么要用w[n] ? 因为现在要填写的是最后一行,第n行的值代表可选的物品只有最后一个物品时背包的最优解
	*  为什么用w[n]和c一起比较求最小值? 为什么要求出jMax? 为什么要用1..jMax进行循环? 后面会详细解说[AQ1].
	*/
	int jMax=min(w[n]-1,c);    //在本例中,n的当前值是4


	for(int j=1; j <= jMax ; j++)     //具体作用见如下解释
		m[n][j]=0;
	
	/**
	*当前的备忘录矩阵为
	*┌─────────────────────┐
	*│　│　│①│②│③│④│⑤│⑥│⑦│⑧│⑨│
	*├─────────────────────┤
	*│　│　│　│　│　│　│　│　│　│　│　│
	*├─────────────────────┤
	*│⑴│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑵│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑶│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑷│　│0 │V │V │V │V │V │V │V │V │
	*└─────────────────────┘
	*
	*   点(⑷,①)变成为0，表示当背包的容量为1，可选物品为⑷时，最优解为0,代表背包中不能放入任何物品。
	*   现在可以回去看看物品的重量数组，很轻松的就看出来了(最轻的重量为2)。
	*   ┌┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┐
	*   ┆现在来解决上面提出的问题[AQ1] :                                                                   ┆
	*	┆  将w[n]-1与c比较,并给jMax[决定了在可选物品只有第n个物品时，背包的容量 <= jMax时,不能放入任何物品，    
	*	┆ 	即最优解为0]
	*   ┆     更具体解释:1.如果min()函数计算后返回的结果为:jMax=w[n]-1
	*   ┆                        (例中的值为1) --> 说明当背包容量<= 1，可选择物品只有4时，不能放入任何物品
	* 　┆　　　　　　　　　      同时，能能过重量数组也可以轻松看出，背包容量 > = 1时，最后一个物品不能放入.
	*	┆				  2.如果min()函数计算后返回的结果为:jMax=c
	*	┆				         则说明最后一个物品重量 > 背包的容量，也不能放入.故在可选物品只有4的情况下，
	*	┆						 背包的容量 <= c 里，最优解为0
	*	┆						 假如最后一个物品的重量为25即 w[n]=25;则最后一行的应如下
	*	┆						┌─────────────────────┐
	*	┆						│⑷│　│0 │0 │0 │0 │0 │0 │0 │0 │0 │
	*	┆						└─────────────────────┘
	*	┆						表明在只有可选物品为4时，背包的容量在小于c任何情况下,都不能放入，最优解为0;
	*   ┆                                                                                                  ┆
	* 　└┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┘
	*/

	
	for(j=w[n]; j <= c ; j++)   //具体作用见如下解释
		m[n][j]=v[n];

	/**
	*当前的备忘录矩阵为
	*┌─────────────────────┐
	*│　│　│①│②│③│④│⑤│⑥│⑦│⑧│⑨│
	*├─────────────────────┤
	*│　│　│　│　│　│　│　│　│　│　│　│
	*├─────────────────────┤
	*│⑴│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑵│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑶│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑷│　│0 │9 │9 │9 │9 │9 │9 │9 │9 │
	*└─────────────────────┘
	* 该循环从w[n]开始到容量c，设置最后一行未求出的最优解V设置为最后一个物品的价值.
	* 图中最后一行所有的9是最后一个物品的价值:代表当可选为⑷, 物品为背包的容量为2..9时，可以将最后一个物品放入.
	*      （请注意查看本程序使用的事例数据） 
	*/

	/**    (第一段的看明白后，有利于后面程序的理解)
	*----------------------------第一段(End)----------------------------------------------
	*/


	/**
	*----------------------------第二段(Begin)----------------------------------------------
	*该程序主要是利用第一行求出的结果并随着可加入物品的增加，来完成备忘录矩阵除第一行外的其它行
	*在该事例程序中，循环共执行两次 每次执行后的结果分别为
	*【第一次】
	*┌─────────────────────┐
	*│　│　│①│②│③│④│⑤│⑥│⑦│⑧│⑨│
	*├─────────────────────┤
	*│　│　│　│　│　│　│　│　│　│　│　│
	*├─────────────────────┤
	*│⑴│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑵│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑶│　│0 │9 │9 │9 │9 │9 │9 │13│13│
	*├─────────────────────┤
	*│⑷│　│0 │9 │9 │9 │9 │9 │9 │9 │9 │
	*└─────────────────────┘
	*【第二次】
	*┌─────────────────────┐
	*│　│　│①│②│③│④│⑤│⑥│⑦│⑧│⑨│
	*├─────────────────────┤
	*│　│　│　│　│　│　│　│　│　│　│　│
	*├─────────────────────┤
	*│⑴│　│V │V │V │V │V │V │V │V │V │
	*├─────────────────────┤
	*│⑵│　│0 │9 │9 │9 │9 │17│17│17│17│
	*├─────────────────────┤
	*│⑶│　│0 │9 │9 │9 │9 │9 │9 │13│13│
	*├─────────────────────┤
	*│⑷│　│0 │9 │9 │9 │9 │9 │9 │9 │9 │
	*└─────────────────────┘
	*/
	for(int i=n-1;i > 1 ; i--)
	{
		/*
		*比较第i个物品的重量各背包的容量
		*/
		jMax=min(w[i]-1,c);

		/**
	    *该代码在第一次循环的过程中，主要处理 点(⑶,①) 到 点(⑶,⑦)的数据:表明在可选物品为⑶,⑷,背包的容量为1..7时，
		*                                     不能放入物品⑶,当前的最优值同只有物品⑷可放入时的最优值相同.当背包的容量
		*第二次循环的处理过程同第一次一样，在意义上只是可选择的物品多了物品⑵							
		*/
		for(j=1; j <= jMax ; j++)
			m[i][j]=m[i+1][j];
		
		/**该代码在第一次循环的过程中，主要处理 点(⑶,⑧) 到 点(⑶,⑨)的数据:表明在可选物品为⑶,⑷,背包的容量为8..9时，
	     *										可以加入物品⑶,加入后的最优值为只有物品⑷的价值加上物品⑶的价值.即为13
	     *第二次循环的处理过程同第一次一样，在意义上只是可选择的物品多了物品⑵									
	     */
		for(j=w[i]; j <= c; j++)
			m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
	}	
	
	/**
	*----------------------------第二段(End)----------------------------------------------
	*第二段程序执行完成以后，只需要决定第一个物品是不是应该放入，在第三段处理
	*/

	
	/**
	*----------------------------第三段(Begin)----------------------------------------------
	*/

	/*
	*先假设第一个物品不放入
	*/
	m[1][c]=m[2][c]; 

	/*
	*如果背包容量大于第一个物品
	*则此时的最优值决定于 (1)不加入第一个物品 或 (2)不加入上次加入的物品，加入第一个物品  ,最大值。就是最后背包的最优解.
	*/
	if(c > w[1])      
		m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

	/**
	*----------------------------第三段(End)----------------------------------------------
	*/

}

/*
*生成向量数组，决定某一个物品是否应该放入背包
*/
void Traceback(int m[][C+1],int w[],int c,int n,int x[])
{
	for(int i=1; i < n ; i++)   //比较备忘录矩阵两邻两行(除最后一行)，背包容量为c的最优值.
	{
		if(m[i][c] == m[i+1][c])   //如果当前行的最优值与下一行的最优值相等，则表明该物品不能放入。
			x[i]=0;
		else                      //否则可以放入
		{
			x[i]=1;
			c-=w[i];
		}
	}
	
	/**单独处理最后一行 
	*  (m[n][c] )?1:0; 等同于(m[n][c] != 0)?1:0;  如果最后一个最优值 为0,则最后一物品不能放入，否则可以放入。
	*/
	x[n]=(m[n][c] )?1:0;

}

//主函数
void main()
{	

	//物品的个数 
	int n=4;

	//背包中物品的重量 (第一个为0,是为了程序理解方便)
	int w[]={0,7,4,6,2};

	//背包中物品的价值(第一个为0,是为了程序理解方便)
	int v[]={0,2,8,4,9};
	
	//备忘录矩阵
	int m[5][C+1];
	
	//背包解的向量数组
	int x[5];

	//构造备忘录矩阵
	Knaspack(v,w,C,n,m);

	//求出解的向量数组
	Traceback(m,w,C,n,x);

	//显示解的结果
	cout<<"背包的容量是:"<<C<<"\t物品的数量是:"<<n<<endl;
	cout<<"重量:\t";
	for(int i=1; i <= n ; i++)
		cout<<w[i]<<"\t  ";
	cout<<endl<<"价值:\t";
	for(i=1; i <= n ; i++)
		cout<<v[i]<<"\t  ";
	cout<<endl<<"背包中应放的物品有：";
	int totalW=0;
	int totalV=0;

	//显示可以放入的物品
	for(i=1; i <= n ; i++)
	{
		if(x[i] == 1)
		{
			totalW+=w[i];
			totalV+=v[i];
			cout<<"(重量:"<<w[i]<<",价值:"<<v[i]<<")"<<"  ";
		}
	}
	cout<<endl<<" >>已放入的物品重量总和是:"<<totalW<<"  价值最优解是:"<<totalV;

	
	cout<<endl<<"如果要查看备忘矩阵，请输入y,退出请输入n?";

	//让用户选择是否显示备忘录矩阵
	char t=getchar();
	if(t == 'y')
	{
		for(i=1; i <= n ; i++)
		{
			for(int j = 1 ; j < C+1; j++)
			{
				int temp=m[i][j]>=0?m[i][j]:-1;
				cout<<temp<<"\t";
			}
			cout<<endl<<"----------------------"<<endl;
		}
	}
	else
	{
		exit(-1);
	}
}