0_1背包问题.cpp

算法分析部分

/*
0-1背包问题：
给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为c。
问应如何选择装入背包的物品，使得装入背包中物品的总价值最大。
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。
不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。

此问题的形式化描述为：
给定c>0,wi>0,vi>0,1<=i<=n
要求找出一个n元0-1向量(x1,x2,...,xn),xi属于{0,1},1<=i<=n
使得wixi<=c{1<=i<=n}，而且vixi{1<=i<=n}达到最大。因此
0-1背包问题是个特殊的整数规划问题：
max = vixi总和{1<=i<=n}
其中wixi总和<=c,{1<=i<=n},xi属于{0,1},1<=i<=n
*/

/*
最优子结构：
0-1背包问题具有最优子结构性质，设(y1,y2,...,yn)是所给0-1背包问题的
一个最优解。则(y2,...,yn)是下面相应子问题的最优解
max{vixi和}{2<=i<=n
wixi和{2<=i<=n}<=c-w1y1
xi属于{0,1}，2<=i<=n
*/
/*
递归关系：
设所给0-1背包问题的子问题
max{vkxk}{i<=k<=n}<=j
且wkxk和{k<=i<=n}<=j,xk属于{0,1},i<=k<=n
的最优值为m(i,j)，即m(i,j)是背包容量为j,可选择物品为i,i+1,...,n时0-1背包问题的
最优值。由0-1背包问题的最优子结构性质，我们可以建立计算m(i,j)的递归式如下：
m(i,j) = max{ m(i+1,j),//不拿当前第i个物品
              m(i+1,j-wi)+vi//拿当前第i个物品
			  },j>=wi

       = m(i+1,j), 0 <=j<wi

m(n,j) = vn, j>=wn
       = 0, 0<=j<wn
	   
*/

/*
算法描述：
基于上述讨论，当wi(1<=i<=n)为正整数时，用二维数组m[][]来存储m(i,j)的相应值，
可设计解0-1背包问题的动态规划算法Knapsack如下：
*/

int min( int a, int b )
{
	if ( a < b )
	{
		return a;
	}
	return b;
}

int max( int a, int b )
{
	if ( a > b )
	{
		return a;
	}
	return b;
}

template< class Type >
void Knapsack( Type *v, int *w, int c, int n, Type **m )
{
	int jMax = min(w[n] - 1,c);
	for( int j = 0; j <= jMax; ++j )
	{
		m[n][j] = 0;
	}
	for( j = w[n]; j <= c; ++j )
	{
		m[n][j] = v[n];
	}

	for( int i = n - 1; i > 1; --i )
	{
		jMax = min( w[i] - 1, c );
		for( int j = 0; j <= jMax; ++j )
		{
			m[i][j] = m[i+1][j];
		}
		for( j = w[i]; j <= c; ++j )
		{
			m[i][j] = max( m[i+1][j], m[i+1][j-w[i]] + v[i] );
		}
	}
	m[1][c] = m[2][c];
	if ( c >= w[1] )
	{
		m[1][c] = max( m[1][c], m[2][c-w[1]] + v[1] );
	}
}

template< class Type >
void Traceback( Type **m, int w, int c, int n, int x )
{
	for( int i = 1; i < n; ++i )
	{
		if ( m[i][c] == m[i+1][c] )
		{
			x[i] = 0;
		}
		else
		{
			x[i] = 1;
			c -= w[i];
		}
	}
	//此时的c已经减去前面选择物品的w了
	x[n] = (m[n][c])?1:0;
}
/*
计算复杂性分析：
从计算m(i,j)的递归容易看出，上述算法Knapsack需要O(nc)计算时间，而
Traceback需要O(n)计算时间。
上述算法Knapsack有两个缺点，一个是算法要求所给物品的重量wi(1<=i<=n)是整数。
其次当背包容量c很大时，算法需要的计算时间较多。例如，当c>2^n时，算法Knapsack
需要U(n*2^n)的计算时间。
*/
/*
具体例子：
n = 5
c = 10
w = {2,2,6,5,4}
v = {6,3,5,4,6}
由计算m(i,j)的递归式，当i = 5时，
m(5,j) = 6, j >= 4
       = 0, 0 <= j < 4
该函数是关于变量j的阶梯状函数。由m(i,j)的递归式容易证明，在一般情况下，
对每个确定的i(1<=i<=n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点
是这一类函数的描述特征。如函数m(5,j)可由其两个跳跃点(0,0)和(4,6)唯一确定。
在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。

在变量j是连续变量的情况下，我们可以对每一个确定的i(1<=i<=n)，用一个表p[i]来存储函数
m(i,j)的全部跳跃点。对每一个确定的实数j,可以通过查表p[i]来确定函数m(i,j)的值。p[i]
中的全部跳跃点(j,m(i,j))依j的升序排列。由于函数m(i,j)是关于变量j的阶梯状单调不减函数，
故p[i]中全部跳跃点的m(i,j)值也是递增排列的。

表p[i]可依计算m(i,j)的递归式递归地由表p[i+1]来计算，初始时p[n+1] = {(0,0)}。
事实上，函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi做max运算得到的。
因此函数m(i,j)的全部跳跃点包含于函数m(i+1,j)的跳跃点集p[i+1]与函数m(i+1,j-wi)+vi的跳跃点集
q[i+1]的并集中。易知，(s,t)属于q[i+1]当且仅当wi<=s<=c且(s-wi,t-vi)属于p[i+1]。
因此，容易由p[i+1]确定跳跃点集q[i+1]如下：
q[i+1] = p[i+1](wi,vi) = {(j+wi,m(i,j)+vi)|(j,m(i,j))属于p[i+1]}
另一方面，设(a,b)和(c,d)是p[i+1]并q[i+1]中的两个跳跃点，则当c>=a,且d<b时，(c,d)受控于
(a,b)，从而(c,d)不是p[i]中的跳跃点。除受控跳跃点外，p[i+1]并q[i+1]中的其他跳跃点均为
p[i]中的跳跃点。

由此可见，在递归地表p[i+1]计算表p[i]时，
可由p[i+1]计算出q[i+1].
然后合并表p[i+1]和表q[i+1],
并清除其中的受控跳跃点得到表p[i]
*/

/*
对于上面的例子，初始时候:
p[6] = {(0,0)},(w5,v5)=(4,6)

因此有q[6] = p[6]叉积(w5,v5)={(4,6)}

由函数m(5,j)可知:
p[5] = {(0,0),(4,6)}
又由(w4,v4) = ( 5, 4 );
q[5] = p[5]叉积(w4,v4) = {(5,4),(9,10)}
p[4] = p[5]并q[5]
.
.
.
最后可得到p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c) = 15
综上所述，可设计解0-1背包问题的改进的动态规划算法如下：
*/

template< class Type >
Type Knapsack( int n, Type c, Type v[], Type w[], Type **p, int x[] )
{
	int *head = 0;
	head = new int[n+2];
	//head数组里面记录了
	head[n+1] = 0;
	p[0][0] = 0;
	p[0][1] = 0;
	int left = 0;
	int right = 0;
	int next = 1;
	head[n] = 1;
	for( int i = n; i >= 1; --i )
	{
		int k = left;
		for( int j = left; j <= right; ++j )
		{
			if ( p[j][0] + w[i] > c )
			//决定是否选取地i个包
			{
				break;
			}

			Type y = p[j][0] + w[i];
			Type m = p[j][1] + v[i];
			//p[j][0]记录的是选取j个物件的最大重量
			//p[j][1]记录的是选取j个物件的最大价值
			//选取j个物件后再选取第i个物件的重量
		
			while( k <= right && p[k][0] < y )
			//y记录了最大重量的前j个物品
			//p[next][0]记录前k个物品的最大重量
			//p[k][0]也就是记录了选取k个物件时的最大重量
			{
				p[next][0] = p[k][0];
				p[next++][1] = p[k++][1];
				//选取next的物件时的最大重量和最大价值
			}
			//

			if ( k <= right && p[k][0] == y )
			//如果选第k个重量等于y
			{
				if ( m < p[k][1] )
				//查看选第k个物件总价值是否大于m
				{
					m = p[k][1];
				}
				k++;
			}

			if ( m > p[next-1][1] )
			//如果此时m的价值大于p[next-1][1]
			//则说明找到了在选择next物件时候的最大价值和物件重量
			{
				p[next][0] = y;
				p[next++][1] = m;
			}

			while( k <= right && p[k][1] <= p[next-1][1] )
			{
				k++;
			}
			//继续循环直到找到比最有价值大的k
		}

		while( k <= right )
		{
			p[next][0] = p[k][0];
			p[next++][1] = p[k++][1];
		}
		//为p[next]赋值

		left = right + 1;
		right = next - 1;
		head[i-1] = next;
		//第i个物件的下标是next
		//每一次循环就是要确定第i个物件被选中为提供最大价值时在选多少个物件
		//限制的时候
	}

	Traceback( n,w,v,p,head,x );

	return p[next-1][1];
}

template< class Type >
void Traceback( int n, Type w[], Type v[], Type **p, int *head, int x[] )
{
	Type j = p[head[0]-1][0];
	Type m = p[head[0]-1][1];
	for( int i = 1; i <= n; ++i )
	{
		x[i] = 0;
		for( int k = head[i+1]; k <= head[i] - 1; ++k )
		{
			if ( p[k][0] + w[i] == j && p[k][1] + v[i] == m )
			{
				x[i] = 1;
				j = p[k][0];
				m = p[k][1];
				break;
			}
		}
	}
}

int main()
{
	int n = 5;
	int c = 10;
	int **m = new int*[n+1];
	for( int i = 0; i < n + 1; ++i )
	{
		m[i] = new int[n+1];
		for( int j = 0; j < n + 1; ++j )
		{
			m[i][j] = 0;
		}
	}

	int *w = new int[n+1];
	w[0] = 0;
	w[1] = 2;
	w[2] = 2;
	w[3] = 6;
	w[4] = 5;
	w[5] = 4;

	int *v = new int[n+1];
	v[0] = 0;
	v[1] = 6;
	v[2] = 3;
	v[3] = 5;
	v[4] = 4;
	v[5] = 6;

	//Knapsack( v, w, c, n, m );
	//Knapsack( int n, Type c, Type v[], Type w[], Type **p, int x[] );

	return 0;
}