01背包问题

问题：有n件物品，每件物品重量为w[ i ]，价值为c[ i ]。现有一个容量为V的背包，问如何选取物品放入背包，使背包总价值最大，其中每个物品只有一件。

样例：

1
2
3

n=5 V=8
3 5 1 2 2 // w[ i ]
4 5 2 1 3 / / c[ i ]

显然，对于每件物品有两种选择，暴力解法复杂度为O($2^n$)
用dp[i][v]表示第i件物品放入容量为v的背包，则dp[i][v]的值求解有两种选择：

公式为：dp[ i ][ v ] = max{ dp[ i-1 ][ v ], dp[ i-1 ][ v - w[ i ] ] + c[ i ] }
第i件物品的状态，只与第i-1件物品的状态有关，所以可以通过边界dp[0][v]=0(0<=v<=V)，递推得到整个数组

for(int i=1;i<=n;i++)
{
		for(int v=w[i];w[i]<V;v++)
		{
				dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
		}
}

这样计算得出的dp[ n ][ V ]的值即为最大值
其实上面的代码还可以在空间复杂度上进行优化，可以看出，在计算dp[i+1][v]的值时，dp[i-1][v]的值没有用到，因此不妨直接用一维数组来代替二维数组，枚举方向从1到n,v从V到0，状态转移方程变为：

1	dp[ v ] = max(dp[ v ],dp[ v-w[ i ]]+c[ i ])

for(int i = 1;i <= n; i++)
{
		for(int v = V; v>=w [ i ]; v--)
		{
				dp[ v ] = max(dp[ v ], dp[ v - w[ i ]] + c[ i ]
		}
}

这样得到的最大值，需要在数组dp里面找出最大值，不是dp[ V ]

操作实例