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，对于一些数据已经可以水过了。

但是这样显然基本上不能拿分。

  1. 设一个函数 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 的时候很难被卡，所以可以当作正解来做。

下面附上一份本人的代码： 

#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完全问题，很难有非常优秀的解法。