DP-01背包

动态规划的典型套路：求最大值、最优解、最大、最小、最长、计数等问题。

01背包问题描述：从 M 件物品中取出若干件放入容量为 W 的背包，每件物品的体积为 W1、W2……Wn，对应价值为 P1、P2……Pn，求能装入背包的最大总价值。

暴力递归求解

最直接的思路是用递归枚举"拿"与"不拿"两种选择：

int w[10] = { 1, 4, 3, 0, 0, 0, 0, 0, 0 };
int v[10] = { 4, 6, 3, 0, 0, 0, 0, 0, 0 };


//0 5
int f(int x, int W)
{
	if (W < w[x])return f(x + 1, W);//剩余可用重量 小于当前物体重量

	if (W <= 0)return 0;//剩余重量 返回价值0
	if (x >= 4)return 0;

	int ret = max(f(x + 1, W - w[x]) + v[x], f(x + 1, W));// 拿和不拿

	return ret;
}

DP 表格递推

递归存在大量重复计算，可以用二维数组缓存已计算的结果。递归中重量依次递减、物品 index 从大到小，因此 DP 循环顺序如下：

	for (int xx = num - 1; xx >= 0; xx--)
	{
		for (int ww = 0; ww <= MAX; ww++)
		{
			if (ww < w[xx])
			{
				arr[xx][ww] = arr[xx + 1][ww];
			}
			else
			{
				int a = arr[xx + 1][ww - w[xx]] + v[xx];//拿
				int b = arr[xx + 1][ww];// 不拿
				arr[xx][ww] = max(a, b);
			}
		}
	}