简单地解释一下我怎么想到的：
首先，两个方案共同的剪枝是：
1. 如果空间允许装满，则直接返回全装满的价值
2. 如果即使所有物品都扔进去，还不如目前搜到的最大值，那么直接返回。
为了避免这两件事情的触发，我们可以在最后放一个价值和质量都极大的物品，保证几乎不可能装满，而且没这个物品对应的价值到不了。
然后对于剪枝方案 1 保证前 $99$ 个物品永远装不满背包，就可以保证至少有 $2^{99}$ 的复杂度。
对于剪枝方案 2 我目前想到的做法就是保证价值持续递增，然后就不会被剪枝。这样的代价就是只需要 $\sqrt{m}$ 个物品就满了。
by yummy @ 2020-10-01 00:40:47
@[2018肖伟文](/user/53533) 请在博客加入适当的说明
@[小粉兔](/user/10703) @[chen_zhe](/user/8457) 希望加入数据，有多少题解被卡了你们愿意找就帮忙撤一下
by yummy @ 2020-10-01 00:46:00
卡卡卡
by 云浅知处 @ 2020-10-01 00:47:23
卡卡卡（
by Demoe @ 2020-10-01 00:52:50
卡卡卡
by kradcigam @ 2020-10-01 00:53:37
算了帮忙找一些吧：
```
https://www.luogu.com.cn/blog/ACmachineoier/solution-p1048（第2种）
https://www.luogu.com.cn/blog/2-6-5-3-5/solution-p1048（第2种命中率低到可看作UNAC）
https://yuntianming.blog.luogu.org/solution-p1048（貌似第2种启发式搜索都凉了？）
https://www.luogu.com.cn/blog/atream-com/sui-ji-hua-tan-xin（第2种命中率低）
```
by yummy @ 2020-10-01 00:56:25
前排Orz
by 7KByte @ 2020-10-01 00:57:09
@[Inf_Voltage](/user/119261) 您Orz啥啊，上古原题这是
by yummy @ 2020-10-01 00:58:25
作者并没有说这个复杂度是对的啊（
by FZzzz @ 2020-10-01 01:00:47
@[FZzzz](/user/174045) 但是不附加说明我觉得就会有小朋友真的以为搜索比dp快
毕竟这一期切入点比较低，应该会有小朋友看，然后我不想在J组看到一群30pts
by yummy @ 2020-10-01 01:07:04