longdie探秘龙之谷（NP完全问题）-题解

应该都能看出来这是一个01背包问题吧。 ## 前言 首先提前说明01背包问题是一个NP完全问题。 证明： 如果你采用搜索那么复杂度是非常显然的 $O(2^n)$。 当然可以用DP，复杂度为 $O(nm)$，看起来不像NP完全问题，但是m的大小随着n的增加快速递增，接近指数级别。 所以它是一个NP完全问题。 ## 前 30% 的数据： 这个就是一个裸的 01 背包，不用讲了吧。 ## 对与 n <= 40 的数据： 不难想到**双向搜索**，然后二分一下就可以了。 ## ？分（乱搞） 对于longdie出的题只能乱搞了啊。 我们考虑部分背包问题的做法，可以设价值比为 $v_i/w_i$，那么显然价值比越大越应该取，所以按照价值比拍个序。 但是放到这道题里是显然不对的，随便可以举出反例，但是我们可以采用一些随机化的方法： 1.排序后从每个点开始都进行一次贪心。 这样肯定会增大正确性，但是它也不是对的，但是事实证明这样可以把误差降低到: $1/n*ans$，对于一些数据已经可以水过了。 但是这样显然基本上不能拿分。 2. 设一个函数 $f(x)$ 表示不取这个物品的概率，那么显然对于价值比越大的龙魂它的 $f(x)$ 应该越小，所以我们不妨设 $f(x) = n-i+2 $，具体操作可以这样： 若 $rand()$ % $f(x) == 0$ ，那我就不取，否则取，我们可以做很多次，会使正确性大大提升。 预估得分：0-100分 这样加上前面非常的部分分就可以拿到非常高的分数了。 ## 对于满分做法 继续考虑乱搞，我们可以从复杂度最高的搜索入手，显然搜索的复杂度是 $O(2^n)$。 但是我们可以考虑 $A^*$ 做法。 具体的我们设 $nw$ 为当前已经用的体积，$nv$ 为当前已经用的价值。 那么我们设 $f[num][nw]$ 表示从第 $num+1$ 个物品开始，当前已经用了 $nw$ 的体积，期望能获得的最大价值。 显然这个期望价值只能大不能小，所以我们可以直接把这个表示成部分背包的价值，这样一定比实际上的大。 这个算法的期望复杂度是 $O(k * 2^n)$，其中 k 是一个 大于0小于1的常数。 实际上这个算法在 n<=1000 的时候很难被卡，所以可以当作正解来做。 下面附上一份本人的代码： ```cpp #include <bits/stdc++.h> using namespace std; const int N = 4005; inline int read(int x = 0) { return scanf("%d", &x), x; } int m, n, ans; struct node { int w, v; double wv; } a[N]; inline bool cmp (node x, node y) { return x.wv > y.wv || (x.wv == y.wv && x.v > y.v); } int func(int num, int sw) { register int res = 0; for(register int i = num + 1; i <= n; i ++) { if(sw + a[i].w <= m) { sw += a[i].w, res += a[i].v; } else return res + (m - sw) * a[i].wv; } return res; } void dfs(int num, int nw, int nv) { if(nv > ans) ans = nv; if(num == n + 1) return; if(nw + a[num].w <= m) dfs(num + 1, nw + a[num].w, nv + a[num].v); if(func(num, nw) + nv > ans) dfs(num + 1, nw, nv); } int main() { n = read(), m = read(); for(register int i = 1; i <= n; ++i) { a[i].w = read(), a[i].v = read(), a[i].wv = 1.0 * a[i].v / a[i].w; } sort(a + 1, a + n + 1, cmp); dfs(1, 0, 0); cout << ans << '\n'; return 0; } ``` 当然如果你不写 $A^*$ 而是大力剪枝的话可能也可以过掉，但是我可以增大数据范围或者构造特殊数据，但是 $A^*$ 算法很难被卡。 当然可能某些大佬会更加高级的算法比如凸包优化，这个我表示我不会。 但是凸包优化的复杂度也是很高的。 所以对于NP完全问题，很难有非常优秀的解法。