[Daimayuan] 背包（C++，模拟）

$cc$有一个背包，背包的体积为$w$，有$n$个物品，每一个物品的体积为aia_iai​

$cc$希望将其中的一些物品放入他的背包中，他希望这些物品的体积之和至少是背包体积的一半，并且不超过背包的体积，即 $\lceil w/2\rceil \le sum\le w$

请你帮$cc$判断这些物品中有没有符合条件的物品组合，如果有输出"$YES$", 没有输出"$NO$"

$cc$至少会拿一个物品

输入格式

第一行给出测试样例个数$T$

对于每一个样例:

第一行给出一个$n$和一个$w$，$n$个物品,背包的总体积是$w$

第二行给出一个序列a1,...ana_1,...a_na1​,...an​，代表每一个物品的体积

输出格式

如果有请输出"$YES$", 没有输出"$NO$"

数据范围

1≤t≤1041≤t≤10^41≤t≤104,1≤∑n≤2∗1051≤\\sum{n}≤2*10^51≤∑n≤2∗105,1≤w≤10181≤w≤10^{18}1≤w≤1018,0≤wi≤1090≤w_i≤10^90≤wi​≤109

样例输入1

3
1 3
3
6 2
19 8 19 69 9 4
7 12
1 1 1 17 1 1 1

样例输出

YES
NO
YES

解题思路

学过背包问题的人不要被标题给误导了$qwq$，因为本题背包容量过大根本不能动态规划

我们回归题意，重新出发

我们把物品分为三类：

（1）如果输入的物品体积大于背包容量，对我们来说就没有意义

（2）如果输入物品体积⌈w/2⌉≤wi≤w⌈w/2⌉≤w_i≤w⌈w/2⌉≤wi​≤w，我们就可以输出$YES$

（3）如果输出物品体积wi<⌈w/2⌉w_i<⌈w/2⌉wi​<⌈w/2⌉，我们就累计这类物品的总体积，如果最终总体积大于$\lceil w/2\rceil$，我们就可以输出$YES$

对于第三类，不必担心物品总体积会直接超过$w$，因为我们可以保证wi<⌈w/2⌉w_i<⌈w/2⌉wi​<⌈w/2⌉，即wi≤w/2w_i \\le w/2wi​≤w/2

所以我们就可以在常数的时间复杂度下解决本题~

最后，AC代码如下

#include <iostream>
using namespace std;
const int max_t = 1e4;
const int max_n = 2e5;
const long long max_w = 1e18;
const int max_item = 1e9;long long t, n, w;int main() {cin >> t;for (int i = 0; i < t; i++) {cin >> n >> w;long long item, sum = 0, ans = 0;for (int i = 0; i < n; i++) {cin >> item;if (item <= w) {if (item >= (w + 1) / 2) ans = 1;else {sum += item;if (sum >= (w + 1) / 2) ans = 1;}}}if (ans) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}