#3857. [GESP202512 六级 C++] 第 14 题

[GESP202512 六级 C++] 第 14 题

0/1 背包(每件物品最多选一次)问题通常可用一维动态规划求解,核心代码如下。则下面说法正确的是( )。

for each item (w, v):
    for (int j = W; j >= w; --j)
        dp[j] = max(dp[j], dp[j-w] + v);

{{ select(1) }}

  • 内层 j 必须从小到大,否则会漏解
  • 内层 j 必须从大到小,否则同一件物品会被用多次
  • j 从大到小或从小到大都一样
  • 只要 dp 初始为 0,方向无所谓