背包问题

0-1背包问题

问题描述：
有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？(对于每个物品不可以取多次，最多只能取一次，之所以叫做0-1背包，0表示不取，1表示取)
此题的每个物品的数量是有限的，对于每个物体只有两种可能，要么不取，要么取。
状态转移方程为：

dp[i+1][j]=dp[i][j] ( j < w[i] ); //即第i个物品的重量太大，不选
dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])( 其他 ) //即第i个物品满足，可以选择，也可以不选择；

其中dp[i+1][j]表示从前i个物品中选出总重量不超过j的物品时总价值的最大值，且dp[0][j]=0。

代码：

c++

##include<iostream>
#include<string.h>
#include<math.h>
#define MAXN 10010
int dp[MAXN][MAXN];
int n;
int W;
int w[MAXN],v[MAXN];
using namespace std;
void solve()
{
	for(int j=0;j<=W;j++)
	{
		dp[0][j]=0;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=W;j++)
		{
		if(j<w[i])
		{
			dp[i+1][j]=dp[i][j];
		}
		else
		{
			dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
		}
	}
	}
	printf("%d\n",dp[n][W]);
}
int main()
{
	cin>>n>>W;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	solve();
	return 0;
}

此时的时间复杂度为: O（nW）;

完全背包问题

完全背包问题与0-1背包问题的区别在于完全背包的每个物品的数量为固定数量，因而转移状态方程发生了变化：

dp[i+1][j]=max{dp[i-kw[i]]+kv[i] | 0<=k}
dp[0][j]=0;

其中dp[i+1][j]表示从前i种物品中挑选总重量不超过j时总价值的最大值。
代码:

c++

#include<iostream>
#include<string.h>
#include<math.h>
#define maxn 101
using namespace std;
int dp[maxn][maxn];
int n,m,k;
int W;
int w[maxn];
int v[maxn];
void solve()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=W;j++)
		{
			for(int k=0;k*w[i]<=j;k++)
			{
				dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
			}
		 } 
	}
	printf("%d\n",dp[n][W]);
}
int main()
{
		cin>>n>>W;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	solve();
	return 0;
}

此时形成了一个三重循环，时间复杂度为O(nW^2),显然不够好，从状态转移方程以及方程意义来看，其中在dp[i+1][j]的计算中选择k(k>=1)的情况，与在dp[i+1][j-w[i]]的计算结果中选择k-1个的情况是一样的，这就造成了大量的重复计算，对状态转移方程进行化简：

max{dp[i][j-kw[i]]+kv[i]|0<=k}
= max(dp[i][j],max(dp[i][j-kw[i]]+kv[i]|k>=1))
= max(dp[i][j],max{dp[i][j-w[i]-kw[i]]+kv[i]|k>=0}+v[i]
= max(dp[i][j],dp[i+1][j-w[i]]+v[i])

根据化简结果可得优化后的代码为：

c++

#include<iostream>
#include<string.h>
#include<math.h>
#define maxn 101
using namespace std;
int ap[maxn][maxn];
int n,m,k;
int W;
int w[maxn];
int v[maxn];
void solve()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=W;j++)
		{
		if(j<w[i])
		{
			dp[i+1][j]=dp[i][j]; 
		}
		else
		{
			dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
		}
		}
	}
	printf("%d\n",dp[n][W]);
}
int main()
{
		cin>>n>>W;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	solve();
	return 0;
}

此时的时间复杂度与0-1背包相同为：O (nW)

空间优化

对于上述的两个问题O (nW)的时间复杂度已经是最优化的状态了，但代码的空间复杂度还可以进行优化。观察上述代码可以将表示状态转移方程的二维数组化为一位，代码如下：
0-1背包问题：

c++

#include<iostream>
#include<string.h>
#include<math.h>
#define MAXN 10010
int dp[MAXN];
int n;
int W;
int w[MAXN],v[MAXN];
using namespace std;
void solve()
{
	for(int i=0;i<n;i++)
	{
		for(int j=W;j>=w[i];j--)
		{
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
	}
	printf("%d\n",dp[n][W]);
}

完全背包问题：

c++

#include<iostream>
#include<string.h>
#include<math.h>
#define MAXN 10010
int dp[MAXN];
int n;
int W;
int w[MAXN],v[MAXN];
using namespace std;
void solve()
{
	for(int i=0;i<n;i++)
	{
		for(int j=w[i];j<=W;j++)
		{
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
	}
	printf("%d\n",dp[n][W]);
}

由上面的两个代码比较可知一维数组的0-1和完全背包问题的区别仅在于循环的方向，那么为什么0-1背包的方向为逆序而完全背包为正序呢？原因还是在于状态转换方程。对于0-1背包问题来说：dp[i+1][j]=dp[i][j] or dp[i][j-w[i]+v[i],现状态由且仅由上一个状态的转换方程决定，因而j从W开始，此时的dp[j-w[i]]+v[i]所代表的值由于j是从大到小的顺序，j的每一个取值的结果都是由上一个状态的值推出，但对于完全背包问题：dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]),其结果是由当前状态推出。因而j的取值需要从小到大进行，有本次状态转移方程的值推出后续的本次状态转移方程的值，因而会存在逆序的差异。