背包问题代码的时间和空间复杂度分析

背包问题代码的时间和空间复杂度分析

本文分析以下代码的时间复杂度和空间复杂度：

int knapasck(int n, int C)
{
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= C;j++)
		{
			if (j < w[i])
				m[i][j] = m[i - 1][j];
			else
				m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
		}
	}
	return m[n][C];
}

时间复杂度

代码中包含两个嵌套循环，外层循环遍历 n 次，内层循环遍历 C 次。因此，代码的时间复杂度为 O(nC)。

空间复杂度

代码中开辟了一个 n × C 的二维数组 m 用于存储中间结果。因此，代码的空间复杂度为 O(nC)。