g6-07451. 复杂度·两重循环的开销核算 未做

$n=1000$ 件物品、容量 $W=100000$。若用二维数组 dp[1001][100001]（每个格子占 4 字节）求解，关于时间开销和内存开销的说法，正确的是（ ）。

• A. 时间按 $O(nW)$ 约为 $10^8$ 次基本运算，尚可接受；但二维数组约需 400 MB 内存，通常超出限制——换成一维后只需约 0.4 MB
• B. 时间 $O(nW)$，内存 $O(n+W)$，两样都很轻松
• C. 时间 $O(n^2)$，与容量 $W$ 无关，内存 $O(n)$
• D. 时间 $O(nW)$；内存恰为 $1000\times 100000=100000000$ 字节