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;
}

然后利用数组来存储已经计算过了的值，，递归到需要返回的时候

因为递归式的重量是依次递减，然后递推至最大

物品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);
			}
		}
	}