招银云创笔试记录：基础选择题与 01 背包

《面试题目》

1. 在每件物品最多选择一次的条件下，如何求容量限制内的最大价值？

《参考解析》

原帖记录了 25 道基础选择题、2 道代码填空和 1 道 01 背包算法题。选择题涉及算法、数据结构、Java 与 Linux，但没有给出完整题干，因此不补造题目。

01 背包状态更新

令 dp[c] 表示容量不超过 c 时能得到的最大价值。处理重量 w、价值 v 的物品时，用 dp[c-w]+v 更新 dp[c]。一维数组必须从大容量向小容量遍历，才能确保当前物品只使用一次；正向更新会读到本轮刚写入的状态，变成允许重复选取。

复杂度为 O(nC) 时间、O(C) 空间。若题意是必须恰好装满，则只有 dp[0] 初始化为零，其他状态应初始化为不可达，不能沿用全部为零的写法。