共63道题，当前是第60题
1 #include <bits/stdc++.h> 2 using namespace std; 3 int w[35000], d[35000], dp[35000]; 4 int main(){ 5 int n, m; 6 scanf("%d%d", &n, &m); 7 for (int i = 1; i <= n; ++i) 8 scanf("%d%d", &w[i], &d[i]); 9 for (int i = 1; i <= n; ++i){ 10 for (int j = m; j >= w[i]; j--){ 11 dp[j] = max(dp[j], dp[j - w[i]] + d[i]); 12 } 13 } 14 printf("%d\n", dp[m]); 15 return 0; 16 }
1. F。若更改则变为完全背包，显然不正确。
2. T。容易知道物品的枚举顺序没有影响。
3. T。30000*30000<=INT_MAX ，不会溢出。
4. D。
5. D。判断方法同上。
6. C。复杂度上限决定于枚举物品及体积的循环，易知答案为O(nm)。
上述代码中，双重循环里循环变量 $j$ 的枚举顺序改为从 $w[i]$ 到 $m$，输出结果一定不变。（ ）
上述代码中，双重循环中变量 $i$ 的枚举顺序改为从 $n$ 到 $1$，输出结果一定不变。（ ）
若输入数据中，$1 \leq n \leq 30000, 1 \leq m \leq 30000, 1 \leq w[i] \leq 30000, 1 \leq d[i] \leq 30000$,则所求答案一定没有溢出。（ ）
当输入为：
4 6
1 4
2 6
3 12
2 7
输出为( )
若输入数据中，$1 \leq n \leq 30000, 1 \leq m \leq 30000, 1 \leq w[i] \leq 30000$,下列给出的 $d[i]$ 的范围，哪个选项所求答案有可能会超出 $INT$ 的范围（ ）
上述代码的时间复杂度为（ ）