动态规划 - 背包问题

问题

有一个背包，最大容量为P，现有数量为S的一堆物品，其大小和价值各不相同，求如何保证背包所装物品价值最高。物品大小与价值由数组w[S]和v[S]给出。

分析

类似问题如果用暴力求解时间复杂度将不可接受。分析问题发现，对于选定的物品，其状态只有两种 – 拿走或放弃，这是一个很明显的动态规划问题。设dp[i][j]为剩余可选物品数量 i 和剩余空间 j 时的物品价值，则很显然有状态方程：dp[i][j] = max[dp[i - 1][j], dp[i - 1][j - w[i-1]]+v[i-1]]. 前者对应放弃物品，因此背包剩余容量不变。后者对应拿走物品，背包容量减少，总价值加上选中物品价值。

代码

C++

int dp[S+1][P+1];
int pick[S];	//保存选中物品
//初始化
for(int i=0;i<S;i++)
	pick[i]=0;
for (int i = 0; i <= S; i++)
	dp[i][0] = 0;
for (int i = 0; i <= P; i++)
	dp[0][i] = 0;
//DP
for (int i = 1; i <= S; i++)
	for (int j = 1; j <= P; j++)
	{
		if (j < w[i - 1])	//背包空间不足
		{
			dp[i][j] = dp[i - 1][j];
			continue;
		}
		else
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
	}
//反向查找选中物品
int j = P;
for (int i = S; i >0; i--)
{
	if (dp[i][j] > dp[i - 1][j])
	{
		pick[i - 1] = 1;
		j -= w[i - 1];
		if (j<=0)
			break;
	}
}

难点：从剩余物品中取时容易理解成贪心算法，每一步DP实际上是从第一个物品选到当前物品