#include<bits/stdc++.h> using namespace std; #define N 35 #define M 205 int m, n, dp[N][M], w[N], c[N]; int main() { cin >> m >> n; for (int i = 1; i <= n; ++i) cin >> w[i] >> c[i]; for (int i = 1; i <= n; ++i) for (int j = 0; j <= m; ++j) { if (j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i]); else dp[i][j] = dp[i - 1][j]; } cout << "max=" << dp[n][m]; return 0; }二维改成一维

下面是将二维数组dp改为一维数组的改进版本：

#include<bits/stdc++.h>
using namespace std;
#define N 35
#define M 205
int m, n, dp[M], w[N], c[N];
int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; ++i)
		cin >> w[i] >> c[i];
	for (int i = 1; i <= n; ++i)
		for (int j = m; j >= w[i]; --j) {
			dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
		}
	cout << "max=" << dp[m];
	return 0;
}

这个改进版本使用一维数组dp来保存状态转移的结果，其中dp[j]表示背包容量为j的情况下，能够获得的最大价值。

在内层循环中，我们从大到小遍历背包容量j，这样确保在计算dp[j]时，dp[j-w[i]]已经被更新过。通过状态转移方程`dp[j] = max(dp[j], dp[j - w[i]] + c[i])`更新dp数组的值。

最后，输出dp[m]作为最大价值结果。

这个改进版本的时间复杂度仍然是O(nm)，但空间复杂度从O(nm)减少到O(m)。这是因为我们只需要保存当前和上一行的状态，所以只需要一个一维数组来存储状态转移的结果。

相关问题

#include <bits/stdc++.h> using namespace std

这段代码是一个C++的头文件引用和命名空间的使用示例。具体来说，`#include <bits/stdc++.h>`是一个常用的头文件引用方式，它包含了C++标准库中的所有头文件。而`using namespace std`则是为了使用`std`命名空间中的标准库函数和对象，这样就可以直接使用`cout`、`cin`等标准输入输出流对象，而不需要写`std::cout`、`std::cin`。

这种写法虽然方便，但也存在一些问题。首先，包含了所有的标准库头文件可能会导致编译时间变长。其次，使用了`using namespace std`会将整个`std`命名空间中的所有标识符引入当前作用域，可能会导致命名冲突。因此，在实际开发中，建议根据需要只包含需要的头文件，并使用具体的命名空间来避免潜在的问题。

#include<bits/stdc++.h> using namespace std;

`#include<bits/stdc++.h>` 是一个常见的C++编程中的预处理指令，它包含了C++标准库中的所有头文件。这样做的好处是可以方便地使用标准库中的各种功能，而不需要一个个地引入具体的头文件。

然而，这种写法并不是标准的C++写法，也不被官方推荐使用。因为它包含了太多的头文件，可能会导致编译时间变长，并且可能会引入一些不必要的头文件，增加代码的冗余性。

推荐的做法是根据实际需要，只包含需要使用的具体头文件，这样可以提高编译效率并减少代码冗余。