Problem C: [CSP-S1][程序阅读] 程序阅读8
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：43
Solved：7
Description
|
int knapSack(int W, int wt[], int val[], int n) { int dp[W+1] = {0}; for (int i = 0; i < n; ++i) for (int j = W; j >= wt[i]; --j) dp[j] = max(dp[j], dp[j-wt[i]] + val[i]); return dp[W]; } |
判断题
1. 该代码实现了0/1背包的空间优化版本。（ ）
2. 若将内层循环改为`j=wt[i]; j<=W; ++j`，结果不变。（ ）
3. `dp[j]`表示容量为j时的最大价值。（ ）
4. 初始化`dp[0]=1`会导致错误答案。（ ）
5. 该算法时间复杂度为O(nW)。（ ）
选择题
6. 若`W=5, wt=[2,3], val=[1,2]`，返回值是：
A. 1 B. 2 C. 3 D. 4
7. 若物品无限使用，需如何修改代码？
A. 内层循环改为正序 B. 外层循环改为正序
C. 无需修改 D. 无法实现
8. 若`W=0`，函数返回：
A. 0 B. -1 C. 未定义 D. 报错
9. 空间优化的依据是：
A. 状态转移只依赖上一层 B. 完全背包特性
C. 贪心选择 D. 分治思想
10. 若所有`val[i]=0`，返回值是：
A. 0 B. W C. n D. -1