题目

在01背包中，问题是这样的：一共有 N 件物品，第 i（i 从 1 开始）件物品的重量为 w [i]，价值为 v [i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？

但现在我们不但需要知道能够装入背包的最大价值，并且需要具体知道是哪些物品呢？

例如背包容量为8，4件物品：

根据状态方程我们可以得出：

背包容量为8时，背包所能装下的最大价值为10;//dp[4][8]

状态转移方程是是这样的：

装入第 i 件物品：dp [i][j]=v [i]+dp [i-1][j-w [i]];
不装第 i 件物品：dp [i][j]=dp [i-1][j];

那我们从dp[4][8]开始回溯，对于编号为4的物品，我们知道有装和没装两种情况，如果没有装，那么它的最大价值应该是等于前3和物品的最佳组合的最大价值，即dp[3][8],而现在dp[3][8]!=dp[4][8],很明显当前应该是装入了4号物品；此时剩下的体积为8-5=3；所以此时我们只考虑前3件物品在体积为3时的最大价值，也就是dp[3][3]=4;以此类推；3号物品没有被装入，2号物品被装入，1号物品没有被装入；

所以装入的是2号、4号物品，最大价值为10

回溯代码：

void solv(int x, int tv)//x为物品编号，tv为体积
{
	if (x==0||tv==0)
	{
		return ;
	}
	else
	{
		if (dp[x][tv]!=dp[x-1][tv])
		{
			cout << x << " ";//输出物品编号
			solv(x - 1, tv - v[x]);
		}
		else
		{
			solv(x - 1, tv);
		}
	}
}