RT

这道题我们需要把DP数组初始化为正无穷大，有两种初始化选择：

• 0x7fffffff
• 0x3f3f3f3f

你或许会觉得两者都能用，但大错特错！

当我们把初始值设为0x7fffffff时，我们会发现，答案给出了一个极其小的负数

代码：

#include <bits/stdc++.h>
#define MAX_SUM 0x7fffffff
using namespace std;

int m, n, ans=MAX_SUM, w[110], v[110], dp[500010];

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m+5000; ++i) {
		dp[i] = MAX_SUM;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> w[i] >> v[i];
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = w[i]; j <= m+5000; ++j) {
			dp[j] = min(dp[j], dp[j-w[i]]+v[i]);
		}
	}
	for (int i = m; i <= m+5000; ++i) {
		ans = min(ans, dp[i]);
	}
	cout << ans << endl;
	return 0;
}

它的值应为：-2147483641

（也有可能为-2147483646）

在询问度娘后，我们会发现这是32位int的最小值

这下就明白了，是我们的初始值太大，导致整形溢出了（C++中，数据超出数据类型范围会变为这个数据类型的最小值）

那让我们再试试0x3f3f3f3f

代码：

#include <bits/stdc++.h>
#define MAX_SUM 0x3f3f3f3f
using namespace std;

int m, n, ans=MAX_SUM, w[110], v[110], dp[500010];

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m+5000; ++i) {
		dp[i] = MAX_SUM;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> w[i] >> v[i];
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = w[i]; j <= m+5000; ++j) {
			dp[j] = min(dp[j], dp[j-w[i]]+v[i]);
		}
	}
	for (int i = m; i <= m+5000; ++i) {
		ans = min(ans, dp[i]);
	}
	cout << ans << endl;
	return 0;
}

（我是不会告诉你这个代码就是把初始值改了一下的）

我们再试一下，惊奇的发现居然AC了！

---

原因

0x7ffffff和0x3f3f3f3f理论上都是32位int的无穷大值，但它们的十进制数字是不一样的：

• 0x7fffffff = 2147483647
• 0x3f3f3f3f = 1061109567

可以发现，两个数都是$10^9$级别的大数，0x7ffffff的十进制值刚好是32位int的最大值，而0x3f3f3f3f的十进制值并不是int的最大值

所以：

当我们只要给初始值为0x7fffffff加上哪怕只是1，整形就会溢出

而0x3f3f3f3f虽然较小，但基本上所有int类型的数据也不会大于它了，并且它哪怕再加上一个它自己，也不会溢出

(1061109567 + 1061109567 = 2122219134)

总结

0x7fffffff非常非常容易（基本上就会）溢出， 最好别用！

0x3f3f3f3f不容易溢出，放心用！

---

附问题

在垃圾堆 CSDN 搜索此问题时，发现一种把数组利用memset初始化为无穷大的方法：

memset(a, 0x3f, sizeof(a));

原因是0x3f3f3f3f的每个每个字节都是0x3f

但在本题我的代码上实验后，却无法给出正确答案

不知能否有神犇解答疑惑