浅谈ZKP问题
renshale
2020-04-22 08:47:42
# 前言
由于作者是一个初二蒟蒻，有一些地方可能存在问题，请多指教。~~喷轻点~~（~~ZXJ不要打我啦~~）
其实，$ZKP$**问题就是背包问题中的$01$背包问题**（也就是说，下文中的01背包等价于$ZKP$问题），但是本文不只是介绍这个问题最普通的$DP$或记忆化搜索解法，还阐述了$ZKP$问题各种数据范围的解法，以及各种不一样的解决$ZKP$问题的方法（如分支限界法、随机贪心法、元启发式算法等）
$ZKP$问题的定义：
求$ max(\Sigma_{i=1}^nx[i]v[i]\;|\;\Sigma_{i=1}^nx[i]w[i]\leq m)(x[i]\in \left\{0,1\right\}) $
$ZKP$问题为什么是$NP$完全问题：
$(1)$搜索解法的时间复杂度：$ O(\Sigma States) = O(\Pi_{i=1}^n|S|)(x[i]\in S) = O(2^n) $，为指数级别
$(2)$动态规划解法的时间复杂度：$O(nm)$，由于$max\left\{m\right\}$随$2^n$增长，所以在某种意义上，$O(nm)$等价于$O(n * 2^n)$
由于其确定性时间复杂度算法，时间复杂度呈指数级增长，所以该题是一个$NP$完全问题（~~其实不是这样证的，这个只是想说明ZKP没有多项式算法而已，大雾~~）
（评论区DL：《算法导论》上有证明）
## 本文使用变量：
$ f[i][j] $ 或 $ f[j] $ 为$ dp $数组
$ w[i] $ 为重量数组(weight)
$ v[i] $ 为价值数组(value)
$ n $ 为物品个数
$ m $ 为背包大小
前置芝士：$01$背包的$DP$解法
# 1 关于DP的优化（可略过）
### 跳跃点优化
简单来说就是找跳跃点，用跳跃点进行$ DP $，但是由于它的时间复杂度为$ O(min(nm,2^n))$，~~非常无用（一个特判的事）~~，所以不在此进行说明
感兴趣的同学可以[右转](http://www.doc88.com/p-8061670594746.html)
# 2 数据范围不太正常的ZKP问题解法
## 例1（超大背包问题）
数据范围：
$ 1 ≤ n ≤ 40,1 ≤ w[i],v[i] ≤ 10^{15},1 ≤ m ≤ 10^{15} $
思路分析：这道题目由于$ m $过大,无法使用$ dp $，考虑使用搜索，但是由于n达到了40，$ O(2^n) $的时间复杂度仍然会超时，于是我们引入一种新的搜索方法：折半搜索
预处理：我们将数据分成规模相同的两半，两边分别进行搜索，每一种$ w, v $ 都进行保存，得到$ wl[i],vl[i],wr[i],vr[i] $
### 双指针法
将两部分数据以$ w $为关键字从大到小进行排序并去重，设i指针初始指向$ wl $ 的头，j指针初始指向$ wr $的尾，由于当$ wl[i - 1] + wr[j] <= m $ 时 $ wl[i] + wr[j] <= m $ 成立（也就是说与$ i - 1 $合法的 $ j $ 也和 $ i $ 合法，因为$ i $的遍历单调递减），并且当 $ wl[i] + wr[j] > m $ 时 $ wl[i] + wr[j + 1] > m $成立（理由和上面差不多），维护$ max \left\{ vr[j] \right\} $ 与 $ vl[i] $ 进行匹配，更新答案即可
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 41
unsigned long long INF = (1ULL << 63) - 1;
int n;
unsigned long long w[N], v[N];
unsigned long long m, ans;
pair< unsigned long long, unsigned long long > a[1 << (N / 2)], b[1 << (N / 2)];
void solve()
{
int half_n = n >> 1;
for(int i = 0; i < 1 << half_n; i ++)
{
unsigned long long sw = 0, sv = 0;
for(int j = 0; j < half_n; j ++)
{
if(i >> j & 1)
{
sw += w[j];
sv += v[j];
}
}
a[i] = make_pair(sw, sv);
}
sort(a, a + (1 << half_n));
int la = 1;
for(int i = 1; i < 1 << half_n; i ++)
if(a[la - 1].second < a[i].second)
a[la ++]=a[i];
for(int i = 0; i < 1 << (n - half_n); i ++)
{
unsigned long long sw = 0, sv = 0;
for(int j = 0; j < n - half_n; j ++)
{
if(i >> j & 1)
{
sw += w[half_n + j];
sv += v[half_n + j];
}
}
b[i] = make_pair(sw, sv);
}
sort(b, b + (1 << half_n));
int lb = 1;
for(int i = 1; i < 1 << half_n; i ++)
if(b[lb - 1].second < b[i].second)
b[lb ++] = b[i];
int mc = 0;
for (int i = la - 1, j = 0; ~i; i --)
{
for (; j < lb && a[i].first + b[j].first <= m; j ++)
if (b[j].second > mc) mc = b[j].second;
if (a[i].first <= m && mc + a[i].second > ans) ans = mc + a[i].second;
}
printf("%lld\n", ans);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%llu %d", &m, &n);
for(int i = 0; i < n; i ++) scanf("%llu %llu", &w[i], &v[i]);
solve();
return 0;
}
```
所以应该叫“[尺取法](https://www.luogu.com.cn/blog/Nero-Yuzurizaki/chi-qu-fa-xiao-jie)”？
### 二分法
将一部分数据以$ w $为关键字从大到小进行排序并去重，在另一部分用$ lower\_bound $ 二分处理即可
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 41
unsigned long long INF = (1ULL << 63) - 1;
int n;
unsigned long long w[N], v[N];
unsigned long long m, ans;
pair< unsigned long long, unsigned long long > a[1 << (N / 2)];
void solve()
{
int half_n = n >> 1;
for(int i = 0; i < 1 << half_n; i ++)
{
unsigned long long sw = 0, sv = 0;
for(int j = 0; j < half_n; j ++)
{
if(i >> j & 1)
{
sw += w[j];
sv += v[j];
}
}
a[i] = make_pair(sw, sv);
}
sort(a, a + (1 << half_n));
int l = 1;
for(int i = 1; i < 1 << half_n; i ++)
if(a[l - 1].second < a[i].second)
a[l ++]=a[i];
for(int i = 0; i < 1 << (n - half_n); i ++)
{
unsigned long long sw = 0, sv = 0;
for(int j = 0; j < n - half_n; j ++)
{
if(i >> j & 1)
{
sw += w[half_n + j];
sv += v[half_n + j];
}
}
if(sw <= m)
{
unsigned long long tv = (lower_bound(a, a + l,make_pair(m - sw, INF)) - 1) -> second;
ans = max(ans , sv + tv);
}
}
printf("%lld\n", ans);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%llu %d", &m, &n);
for(int i = 0; i < n; i ++) scanf("%llu %llu", &w[i], &v[i]);
solve();
return 0;
}
```
两个方法的效率都差不多，时间复杂度：$ O(2^{\frac{n}{2}} \; log \; 2^{\frac{n}{2}}) = O(\sqrt {2^n} * \frac{n}{2})$ （要相信~~快速的~~$sort$，但$lower\_bound$……）
推荐使用双指针法，二分法常数较大
## 例2（极多物背包问题）
数据范围：
$ 1 ≤ n ≤ 10^6,1 ≤ w[i],v[i] ≤ 50,1 ≤ m ≤ 10^4 $
思路分析：由于$ n * m $ 较大，$ O(nm) $ 的算法无法通过，但我们发现$ w[i], v[i] $ 较小，由于$ max \left\{ w[i] \right\} * max \left\{ v[i] \right\} \leq n $，不同的物品种数也就只有$ max \left\{ w[i] \right\} * max \left\{ v[i] \right\} $种，所以将会有很多同样的物品，这就可以让我们将其转化为多重背包
注意：下文中$ n $的级别被缩小到$ max \left\{ w[i] \right\} * max \left\{ v[i] \right\} $
### 二进制分组法
此法较好理解，根据二进制表示法，$ num[i] $个$ v[i] $可以被分为$ 1,2,4,8,...2^{x-1}(2^x\geq num[i])$个$ v[i] $，所以$ num[i] $个物品可以被分成$ log(num[i]) $个物品
时间复杂度：$ O(nm\Sigma_{i=1}^n log(num[i])) = O(max \left\{ w[i] \right\} * max \left\{ v[i] \right\} * m * \Sigma_{i=1}^n log(num[i]))$ ($ num[i] $ 表示该组物品的个数)，但在此题会超时（被卡？）
### 单调队列法
此法较难理解，主要思想在于将$ DP $转换形式，发现其只与枚举$ num[i] $的变量$ k $有关
时间复杂度：$ O(nm) = O(max \left\{ w[i] \right\} * max \left\{ v[i] \right\} * m)$，为此题正解
（~~noip不考~~）（~~其实作者也不大会~~）
不会的[右转](https://www.luogu.com.cn/blog/RPdreamer/bei-bao-wen-ti)
## 伪例3（小包问题）
数据范围：
$ 1 ≤ n ≤ 10^6,1 ≤ w[i],v[i] ≤ 10^{15},1 ≤ m ≤ 10^3 $
DP，时间复杂度：$ O(nm) $，然而由于$ m $很小，所以可以将$ n $ 缩小成 $ m $ 级别，这样就转换成了多重背包问题（跟例2很像呢，~~所以说标题是伪吗~~……）
由于以上算法涉及多重背包，容易找到资料，故不在此实现
# 3 搜索+剪枝
相信大家最开始做$01$背包的时候，都会用$dfs$，但是由于低效只能拿到部分分数，但是这里的搜索，却可以在一些数据上代替$DP$拿到满分
## 例1
数据范围：
$ 1 ≤ n ≤ 10^2,1 ≤ w[i],v[i] ≤ 10^{15},1 ≤ m ≤ 10^{15} $
来自$ HDU\;5887\;Herbs\;Gathering$（改）
思路分析：这道题看上去，前文所提到的算法都无法很好的解决，~~然而生活中遇到的常常是无法用确定性算法解决的问题~~，所以这题我们采用搜索+剪枝
预处理：按照$ v[i] / w[i] $从大到小排序（网友表示，为什么其它排序都会TLE呢？~~玄学~~）（因为这样有获得更大答案的倾向啊，~~大雾~~）
状态：$ dfs(x, Wnow, Vnow) $：
$ x $ 表示目前搜索到第几个数，
$ Wnow $ 表示目前可用的空间，
$ Vnow $ 表示目前得到的价值；
$ Sumw[i] $ 表示 $ w[i] $ 的后缀和，
$ Sumv[i] $ 表示 $ v[i] $ 的后缀和，
$ ans $ 为当前最大价值
### 剪枝1
当$ Wnow \geq Sumw[x] $ 时，用 $ Vnow + Sumv[x] $ 更新$ ans $，并退出当前递归
意义：如果后面能全部装进去，就直接装
### 剪枝2
当$ Vnow + Sumv[x] \leq ans $时，退出当前递归
意义：如果后面的全部装进去以后，都没当前最优答案大，那就不用装了
### 剪枝3
当$ Vnow + Wnow / w[x] * v[x] \leq ans $ 时，退出当前递归
意义：由于已经排序$ x $ 比 $ x + i $ 要优，把$x $代替$x + i$把背包装满，都没当前最优答案大，那就不用装了
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
struct node
{
int w, v;
double wv;
} a[N];
int n, m, t, ans;
int sumw[N], sumv[N];
inline bool cmp (node x, node y)
{
return x.wv > y.wv || (x.wv == y.wv && x.v > y.v);
}
void dfs(int x, int y, int z)
{
if (x > n)
{
if (z > ans) ans = z;
return ;
}
if (y + sumw[x] <= m)
{
if (z + sumv[x] > ans)
ans = z + sumv[x];
return ;
}
if (z + (double) (m - y) / a[x].w * a[x].v <= ans) return ;
dfs(x + 1, y, z);
if (y + a[x].w <= m)
dfs(x + 1, y + a[x].w, z + a[x].v);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d %d", &a[i].w, &a[i].v);
a[i].wv = (double) a[i].v / a[i].w;
}
sort(a + 1, a + n + 1, cmp);
t = m;
/* for (int i = 1; i <= n; i ++)
if (t >= a[i].w)
{
ans += a[i].v;
t -= a[i].w;
} */
for (int i = n; i > 0; i --)
{
sumw[i] = sumw[i + 1] + a[i].w;
sumv[i] = sumv[i + 1] + a[i].v;
}
dfs(1, 0, 0);
printf("%d", ans);
return 0;
}
```
**实际上这个方法也可以运用于上面的其它问题（万金油）**
下文的贪心初始流可以起到一些~~未知~~的优化
## 例2
数据范围：
$ 1 ≤ n ≤ 10^3,1 ≤ w[i],v[i] ≤ 10^{15},1 ≤ m ≤ 10^{15} $
来自$ Luogu \; P1048 \; Medic $（改）
思路分析：也是搜索+剪枝呢，只不过更强一点
预处理：按照$ w[i] $从小到大排序，对于相同的$ w[i] $，按照$ v[i] $从大到小排序
### 剪枝1
即为上面的剪枝1和剪枝2
### 剪枝2
在dfs时维护$ mv = max\left\{v[x] \; | \; x \; hasn't \; been \;selected \right\}$
当$ v[x] <= mv $ 时，不选$ x $
意义：当$ x $比$ y $优（重量比其小，价值比其大），却没有被选时，$ y $也没有必要选
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
struct node
{
int w, v;
double wv;
} a[N];
int n, m, t, ans, sum;
int sumw[N], sumv[N];
inline bool cmp (node x, node y)
{
return x.w < y.w || (x.w == y.w && x.v > y.v);
}
void dfs(int x, int y, int z, int p)
{
if (x > n)
{
if (z > ans) ans = z;
return ;
}
if (y + sumw[x] <= m)
{
if (z + sumv[x] > ans)
ans = z + sumv[x];
return ;
}
if (y + a[x].w <= m && a[x].v > p)
dfs(x + 1, y + a[x].w, z + a[x].v, p);
if (z + sumv[x + 1] > ans)
dfs(x + 1, y, z, a[x].v > p ? a[x].v : p);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d %d", &a[i].w, &a[i].v);
a[i].wv = (double) a[i].v / a[i].w;
}
sort(a + 1, a + n + 1, cmp);
/* for (int k = 1; k <= n; k ++)
{
sum = 0, t = m;
for (int i = k; i <= n; i ++)
if (t >= a[i].w)
{
sum += a[i].v;
t -= a[i].w;
}
if (sum > ans) ans = sum;
} */
for (int i = n; i > 0; i --)
{
sumw[i] = sumw[i + 1] + a[i].w;
sumv[i] = sumv[i + 1] + a[i].v;
}
dfs(1, 0, 0, 0);
printf("%d", ans);
return 0;
}
```
~~由于某种未知的原因~~，**例2所用的解法比例1要优，所以推荐使用例2的方法**
# 4 奇妙的ZKP问题解法
在下文中，我们把一个物品的 $ v[i] / w[i] $ 称为价值比
随机次数变量为 $ T $
平均搜索常数为 $ K $（所有从根到叶子搜索过的路径条数）
## 铺垫：贪心法
前言：大家在01背包的问题中，很容易想到贪心算法，因为正常人都知道，价值比大的物品放进背包里更优，这在部分背包（可以将物品的一部分放入背包中的背包问题）里是正确的，但是在01背包中，我们还要考虑背包的剩余空间是否能装下整的一个物品，所以这个方法可以构造出许多反例，但是由于其提供了一个别样的思路，所以对下文的许多算法得实现都造成了启发。
方法：将$ w[i], v[i] $ 以 $ v[i] / w[i] $ 为关键字（也可以换成 $ v[i] $ 或者 $ w[i] $ )从大到小排序，从头到尾依次取可以放入背包的物品。
### 拓展：k阶优化方法(k-optimal)
由于从头至尾的贪心不一定最优，我们可以考虑换一个起点进行贪心，获得更优解，通过实际测试得出（~~因为论文里没讲~~），更换$ k (k \leq n) $次起点可以使期望**误差**上界达到$ \frac{1}{k + 1} * ans $，实际性能会更好
以下给出普适版的$ O(n^2) $实现：
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
struct node
{
int w, v;
double wv;
} a[N];
int n, m, t, ans, sum;
inline bool cmp (node x, node y)
{
return x.wv > y.wv || (x.wv == y.wv && x.v > y.v);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d %d", &a[i].w, &a[i].v);
a[i].wv = (double) a[i].v / a[i].w;
}
sort(a + 1, a + n + 1, cmp);
for (int k = 1; k <= n; k ++)
{
sum = 0, t = m;
for (int i = k; i <= n; i ++)
if (t >= a[i].w)
{
sum += a[i].v;
t -= a[i].w;
}
if (sum > ans)
ans = sum;
}
printf("%d", ans);
return 0;
}
```
**注意：从$ dfs\_spfa $的优化中获得启发，可以利用贪心法获得一个较优的初始解，从而一定程度上优化某些方法的效率（如下文的分支限界法），这被称作贪心初始流**
## 贪心 + 概率随机法
前置条件：在上文的贪心的基础上，我们得知一个事实，虽然价值比大的物品不一定优先放入背包，但是它放入背包的概率比其它物品的概率更大。
方法：所以我们可以构造一个概率函数 $ g(i) $，表示一个物品不取的概率，这个概率函数只要满足价值比大的物品更小即可，在这里我们取$ g(i) $ 为 $ \frac{1}{n-i+2} $ ，在实际操作时可以这样实现 ，当$ rand() \; \equiv 0 \; \pmod{(n-i+2)} $时，不取该物品，否则取，进行贪心，由于这种方法带有随机性，所以要多做几次
时间复杂度：$ O(Tn + n log n) $
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
#define Times 100000
struct node
{
int w, v;
double wv;
} a[N];
int n, m, t, ans, sum;
inline bool cmp (node x, node y)
{
return x.wv > y.wv || (x.wv == y.wv && x.v > y.v);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
srand(19260817);
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d %d", &a[i].w, &a[i].v);
a[i].wv = (double) a[i].v / a[i].w;
}
sort(a + 1, a + n + 1, cmp);
for (int T = 1; T <= Times; T ++)
{
sum = 0, t = m;
for (int i = 1; i <= n; i ++)
if (rand() % (n - i + 2) && t >= a[i].w)
{
sum += a[i].v;
t -= a[i].w;
}
if (sum > ans)
ans = sum;
}
printf("%d", ans);
return 0;
}
```
~~东方玄学种子~~
## 贪心 + 优先级随机法
前置条件：同样，在上文的贪心的基础上，我们得知一个事实，虽然排序后的序列不是最优序列，但它是接近最优序列的。
方法：所以我们可以把它的优先级进行微调，如何微调呢？我们引进一个取值范围为$ (0.5,1) $ （其实其它的好像也可以）的随机小数 $ \eta $ ，刚开始时按照价值比排序一遍，得出优先级$ p_i $，再在每次贪心开始前，用 $ p_i * \eta_i $ （$ \eta $ 每次都要更新哦）为关键字重新排序，由于这种方法带有随机性，所以要多做几次
时间复杂度：$ O(Tn log n) $
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
#define Times 10000
struct node
{
int w, v;
double wv, wvl;
} a[N];
int n, m, t, ans, sum;
inline bool cmp (node x, node y)
{
return x.wv > y.wv || (x.wv == y.wv && x.v > y.v);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
srand(19260817);
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d %d", &a[i].w, &a[i].v);
a[i].wvl = a[i].wv = (double) a[i].v / a[i].w;
}
sort(a + 1, a + n + 1, cmp);
for (int T = 1; T <= Times; T ++)
{
sum = 0, t = m;
for (int i = 1; i <= n; i ++)
if (rand() % (n - i + 2) && t >= a[i].w)
{
sum += a[i].v;
t -= a[i].w;
}
if (sum > ans)
ans = sum;
for (int i = 1; i <= n; i ++)
{
double eta = 0.5 + 0.5 * rand() / RAND_MAX;
a[i].wv = a[i].wvl * eta;
}
sort(a + 1, a + n + 1, cmp);
}
printf("%d", ans);
return 0;
}
```
~~东方玄学种子~~
## 估价函数法
思路分析：由于搜索不能快速的解决问题，我们考虑用人的思维去帮助它，也就是借用$ A^* $的估价函数思想去优化$dfs$
状态：$ dfs(x, Wnow, Vnow) $：
$ x $ 表示目前搜索到第几个数，
$ Wnow $ 表示目前可用的空间，
$ Vnow $ 表示目前得到的价值；
$ ans $ 为当前最大价值
前置条件：我们需要一个合理的估价函数，为了确保正确性，我们要求估价函数的值大于等于实际值，为此我们考虑部分背包的价值作为上界，在$ 1 \sim n $ 的范围中，设 $ r_{1 \sim n} = min \left\{j \; | \; \Sigma_{i=1}^j w[i] > m \right\} $ ，那么上界 $ U_{1 \sim n} = \Sigma_{i=1}^{r-1}v[i] + (m - \Sigma_{i=1}^{r-1}w[i]) * \frac{v[i]}{w[i]} $ ，估价函数$ V(x,Vnow) = Vnow + U_{x \sim n} $ （其实就是说，把后面的东西贪心装进去，装不完的就装一部分，这样保证比实际值要大）
### 剪枝
当 $ V(x,Vnow) < ans $时，退出当前递归
意义：如果该状态可达到的最大价值还没有当前最优解优，就不需要继续了
时间复杂度：$ O(n * 2 ^ n) $，但是由于剪枝的原因，跑不满，所以应该是 $ O(n * Kn) $
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
struct node
{
int w, v;
double wv;
} a[N];
int n, m, t, ans;
int sumw[N], sumv[N];
inline bool cmp (node x, node y)
{
return x.wv > y.wv || (x.wv == y.wv && x.v > y.v);
}
inline int func(int sx, int sw)
{
int res = 0;
for (int i = sx + 1; i <= n; i ++)
{
if (sw + a[i].w <= m)
{
sw += a[i].w;
res += a[i].v;
}
else
return (int) (res + (m - sw) * a[i].wv);
}
return res;
}
void dfs(int x, int y, int z)
{
if (z > ans) ans = z;
if (x > n) return ;
if (func(x, y) + z > ans) dfs(x + 1, y, z);
if (y + a[x].w <= m) dfs(x + 1, y + a[x].w, z + a[x].v);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d %d", &a[i].w, &a[i].v);
a[i].wv = (double) a[i].v / a[i].w;
}
sort(a + 1, a + n + 1, cmp);
dfs(1, 0, 0);
printf("%d", ans);
return 0;
}
```
小优化：如果估价值可以由上一个状态转移而来，时间复杂度应该可以降到$ O(Kn) $（~~作者也没试过，大家可以试一试~~）
## 分支限界法
这个东西好像跟估价函数法差不多，但是改用$bfs+$优先队列（以$ V(x, Vnow)$做优先级），可以优化搜索方向，增快速度（而且避免爆栈）
时间复杂度：$ O(n * Kn) $ （这里的$K$比上面的要小，因为它的剪枝更强力，优先队列的总复杂度是$ O (log\; n * Kn) $，所以不需要计算）
**上面的两个方法使用贪心初始流可以降低$ K $的大小**
## 黑科技：快速降阶法
这是一个神奇的东西，可以成批确定一定在背包最优解中的物品和成批排除一定不在背包最优解中的物品。
具体证明[右转](http://kns.cnki.net/KXReader/Detail?TIMESTAMP=637217770674720000&DBCODE=CJFQ&TABLEName=CJFD2005&FileName=XTGL200504019&RESULT=1&SIGN=DAnaX1l4oeiFSPeWEnuC7yxMJCU%3d)，这里讲过程（以及~~感性~~理解）
（由于这是论文，~~要登录我也没办法~~）
一个背包问题的数据集表示为$ S $，
背包大小表示为$ m $，
上界表示为$ U(S, m) $，
下界表示为$ B(S, m) $，
$ S - \left\{i\right\} $表示去掉$ i $的$ S $集
设 $ r_S = min \left\{j \; | \; \Sigma_{i=1}^j w[i] \leq m \right\} $，$ c_S = min \left\{j \; | \; \Sigma_{i=1}^j w[i] \leq m - w[r+1] \right\} $
$ U $有两种：
$ U_1 = \Sigma_{i=1}^{r}v[i] + (m - \Sigma_{i=1}^{r}w[i]) * \frac{v[r+1]}{w[r+1]}$
$ U_{2_0} = \Sigma_{i=1}^{r}v[i] + (m - \Sigma_{i=1}^{r}w[i]) * \frac{v[r+2]}{w[r+2]}$
$ U_{2_1} = v[r+1] + \Sigma_{i=1}^{c}v[i] + (m - w[r+1] - \Sigma_{i=1}^cw[i]) * \frac{v[c+1]}{w[c+1]}$
$ U_2 = max(U_{2_0},U_{2_1})$
由于$ U_2 $考虑的更加详细，所以我们一般使用$ U = U_2 $，也可以使用$ U = max(U_1,U_2) $
任何一个可行解都可以作为该问题的一个$ B $（但用贪心又快又好）
这里有两种：
$ (1) $ 按照价值比排序，贪心得出$ B_1 $
$ (2) $ 按照 $ v[i] $ 排序，贪心得出$ B_2 $
$ B = max(B_1,B_2) $
预处理：按价值比排序$ w[i],v[i] $
### 快速确定一定在最优解中的物品
$(1)$若$ U(S-\left\{i\right\},V) < B(S,V) $，则物品$ i $一定在最优解中，反之则不能判定
理解：如果没有$ i $的最好情况还不如有$ i $的最坏情况，由于$ U(S-\left\{i\right\},V) \geq B(S-\left\{i\right\},V) $，那么一定选了$ i $
$(2)$在$(1)$中的方法无法判定$ r + 2 $以后的物品
理解：因为上面的式子里最多只影响到第$ r+2$项
$(3)$当用$(1)$的方法确定一个最优解$i$后，在$i$前面的且价值大于$i$的物品都是最优解
理解：因为前面的物品价值比和价值都比$i$大，且$i$都是最优解，如果价值比比i大，但价值比$i$小还没有一定必要选，但两个都比$i$大就一定要选了吧（~~心虚~~）
### 快速确定一定不在最优解中的物品
$(1)$若$ v[i]+U(S-\left\{i\right\},V-w[i]) < B(S,V) $，则物品$ i $一定在最优解中，反之则不能判定
理解：类比上面
$(2)$在$(1)$中的方法无法判定$ r + 2 $以后的物品
理解：类比上面
$(3)$当用$(1)$的方法确定一个最优解$i$后，在$i$后面的且重量大于$i$的物品都是最优解
理解：类比上面（~~心虚~~$* 2$）
以上两个判定方法有两个用处：
$(1)$重复迭代，得到最优解
$(2)$降低$n$的规模，配合其它算法使用
这是一种参考性优化，由于该算法可能还能优化，且实现较自由，故不在此实现
## 凸包剪枝法
**在阅读该篇之前，请确保还记得上文例2的剪枝思想**
这是一位巨佬提供的算法，%%%TQL（该算法在随机数据下，期望时间复杂度证明成立）
我们从例$2$的算法中得到一点点启发，如果用$bfs$做会怎么样呢？
排序按照$w[i]$由小到大，如果$ w $相同，则按照$ v[i] $由大到小进行排序
维护一个队列，队列中的每个元素维护目前的取值状态所得到的总$ w[i],v[i] $（也就是说维护前$i-1$个物品所构成的所有状态的总重量和价值），我们称其为$ Qw[i], Qv[i]$，队列目前所含有元素个数为$L$
枚举一个$i$，表示目前取到第$i$个数，那么队列需要更新元素，此时多出了$L$个元素，分别表示原来的第$L$个元素取了$i$这个物品，那么$L=L * 2$，并对$Q$进行排序
### 剪枝
排完序以后，我们由$ 1 \sim L $遍历，维护一个$mx = max\left\{Qv[i]\right\}$，当$ Qv[i] \leq mx $时将其删除
意义：重量大，价值又小的状态不用加入队列
（此处可以用一个新队列来实现，确保其在队列中有序）
期望时间复杂度：$ O(n^2 \;log\; n) $
### 优化
当原来的$L$个元素有序时，我们发现新加入的$L$个元素也是有序的（都是加上同一个物品），所以，不需要排序，直接归并就好啦
期望时间复杂度：$ O(n^2) $
### 证明
这里可能有人会问，为什么期望时间复杂度是线性的呢？明明$L$最大可能达到$ 2^n $
但是你要看看，数据是随机的呢，加上了剪枝以后，我们将$ w, v $作为平面的$ x, y $轴，会发现，队列里维护的是$ w[i], v[i] $的上凸壳，而在随机数据下，$ N $个点的凸包上点个数的期望值是$ log \; N$，又因为$ log \; 2^n = n $，所以$L$不会超过$n$
（管理员大大对此提出了不同的看法，我的想法就是，将$w$当做$x$轴，$v$当做$y$轴，那么以一个点作为原点的时候，第四象限的所有点由于$w < w'$以及$v > v'$都可以被筛掉（就是右下角的点都没了），所以在队列中的点一定左上角都是没有点的，好像只有上凸壳的点满足条件，在和dalao的私信中，dalao好像赞同这个想法（雾 ）
关于在随机数据下，$ N $个点的凸包上点个数的期望值是$ log \; N$的证明，[右转](https://zhuanlan.zhihu.com/p/63260925)
[巨佬的代码](https://www.luogu.com.cn/paste/g1dc6nra)（附[题面](https://www.luogu.com.cn/problem/U102618)）
**（完）**
致谢：@$\_26535\_$ @$ Atream $ @$ chenxinyang2006 $ 等巨佬
引用来自百度文库、中国知网及诸多$ \;blog \;$（~~链接大部分来自~~**洛谷日报**）
非常欢迎提出新方法或指出错误