Homework 11 — CS170

作业 11

本次作业包含三个部分：学习小组登记；从子集和（Subset Sum）问题到划分（Partition）问题和背包（Knapsack）问题的线性时间约简证明；以及将集合覆盖（Set Cover）问题约简为整数线性规划（Integer Linear Program）的编程实践。

知识焦点

先建立概念地图

reduction
subset sum
partition
knapsack
integer linear programming
set cover
NP-completeness
约简

建议顺序

题面 → 提示 → 答案

先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。

本地来源

可离线完成

题面与解答均由本地一手资料整理：hw11.pdf、hw11-sol.pdf

本地一手资料完整提取 · 作业

完整题目、提示与答案

本节按本地一手资料完整整理，共 3 道大题。本地官方解答已收录 1/3 道并默认折叠；其余题目会明确标注无本地官方解答。

使用说明

所有题面均已本土化，并补足网页离线作答所需的数值、代码、表格与约束。
题目与答案分层展示，展开答案前可先查看提示。
本地来源：hw11.pdf、hw11-sol.pdf

1学习小组题目 · 提示 · 答案

官方题面翻译可离线作答无本地官方解答

完整题面

列出你的学习小组中所有成员的姓名和 SID（学生编号）。如果你没有合作者，必须明确写出 "none"。

查看解题提示

本题无需数学提示，如实填写即可。

答案状态

本地资料未提供这道题的官方解答；页面只保留题面与非答案式提示。

题面来源：hw11.pdf · 1 · confidence: high

2一些求和问题（约简证明）题目 · 提示 · 答案

官方题面翻译可离线作答官方解答已收录

完整题面

给定一个非负整数数组 \(A = [a_1, a_2, \dots, a_n]\)，考虑以下问题：

划分（Partition）：判断是否存在子集 \(S \subseteq [n]\)（其中 \([n] := \{1, 2, \dots, n\}\)），使得 \[ \sum_{i \in S} a_i = \sum_{j \in [n] \setminus S} a_j. \] 换句话说，判断是否能将 \(A\) 划分为两个不相交的子集，使得每个子集的元素之和相等。
子集和（Subset Sum）：给定某个整数 \(k\)，判断是否存在子集 \(S \subseteq [n]\)，使得 \[ \sum_{i \in S} a_i = k. \] 换句话说，判断是否存在 \(A\) 的一个子集，其元素之和等于 \(k\)。
背包（Knapsack）：给定一组物品，每个物品有重量 \(w_i\) 和价值 \(v_i\)，以及固定数值 \(W\) 和 \(V\)，判断是否存在某个子集 \(S \subseteq [n]\)，使得 \[ \sum_{i \in S} w_i \leq W \quad \text{且} \quad \sum_{i \in S} v_i \geq V. \]

对于下面的每个问题，请清楚描述你的约简（reduction）并证明其正确性。

(a) 给出一个从子集和到划分的线性时间约简（linear time reduction）。

(b) 给出一个从子集和到背包的线性时间约简。

查看解题提示

(a) 考虑在 \(A\) 中添加一个经过精心选择的元素，使得划分后两侧的平衡条件自然迫使某个子集的和恰好等于目标值 \(t\)。注意分情况讨论总和 \(s\) 与 \(2t\) 的关系。

(b) 子集和只关心被选中元素的和，尝试让每个物品的重量与价值相等，从而使背包的两个约束合并为同一个等式约束。

展开官方参考解答

(a) 设给定的数组为 \(A\)，目标和为 \(t\)。令 \(s\) 为 \(A\) 中所有元素之和。

若 \(s - 2t \geq 0\)，则构造新集合 \(A' = A \cup \{s - 2t\}\)。若 \(A'\) 可以被划分，则 \(A\) 中存在一个子集，其元素之和为 \(t\)。

证明：划分后两个子集的元素之和均为 \(s - t\)（因为 \(A'\) 的总和为 \(2s - 2t\)）。其中一个子集必包含元素 \(s - 2t\)，因此该子集中其余元素之和为 \((s - t) - (s - 2t) = t\)。

若 \(s - 2t \leq 0\)，则构造新集合 \(A' = A \cup \{2t - s\}\)。若 \(A'\) 可以被划分，则 \(A\) 中存在一个子集，其元素之和为 \(t\)。

证明：划分后两个子集的元素之和均为 \(t\)（因为 \(A'\) 的总和为 \(2t\)）。不包含元素 \(2t - s\) 的那个子集即为子集和问题的解。

(b) 设给定的集合为 \(A\)，目标和为 \(t\)。对集合中的每个元素，创建一个重量和价值均等于该元素值的物品。令 \(V = t\) 且 \(W = t\)。背包问题将判断是否存在一组物品，其重量之和 \(\leq t\) 且价值之和 \(\geq t\)。因为每个物品的重量与价值相等，所以被选中的物品重量之和等于价值之和，要同时满足 \(\leq t\) 和 \(\geq t\)，只能等于 \(t\)。由于每个物品的重量/价值对恰好对应 \(A\) 中一个原始元素的值，因此背包问题有解当且仅当子集和问题有解。

解答来源：hw11-sol.pdf · 1 · confidence: high

题面来源：hw11.pdf · 1 · confidence: high

3编程题：约简到整数线性规划题目 · 提示 · 答案

官方题面翻译可离线作答无本地官方解答

完整题面

本周的编程题将引导你完成将集合覆盖（Set Cover）问题约简为一个整数线性规划（Integer Linear Program），并展示约简在实际中是如何被使用的。你可以通过以下两种方式访问 notebook 并完成题目：

本地机器：从 coding homework 仓库 git clone（或如果已经克隆过则 git pull） https://github.com/Berkeley-CS170/cs170-fa23-coding 并导航到 hw011 文件夹。参见 README.md 了解本地环境配置说明。
Datahub：点击此处并导航到 hw11 文件夹，如果你更倾向于在 Berkeley DataHub 上完成本题。

注意事项：

提交说明：请下载你完成的提交 .zip 文件，并将其提交到 Gradescope 上名为 "Homework 11 Coding Portion" 的作业中。
Office Hour / Homework Party 说明：指定的编程课程助教将在 office hour 和 homework party 期间提供概念性和调试方面的帮助。
Edstem 说明：公共帖中始终欢迎概念性问题。如果你需要调试帮助，请先在公共帖中提问。为了确保其他人能帮助你，请确保： 1. 描述你在发帖到 Ed 之前已经尝试过的调试步骤。 2. 描述你遇到的具体错误。 3. 提供几个小型测试用例，同时附上你期望得到的输出和你函数的实际输出。

如果助教要求你发私人 Ed 帖，请确保包含上述所有项目以及你的完整函数实现。如果你未提供，我们会要求你补充。

学术诚信指南：我们意识到，我们要求实现的某些算法的代码可能在网上很容易获得，但我们强烈建议你不要直接复制这些来源的代码。相反，请尝试参考 notebook 中提到的资源，自己编写代码。话虽如此，我们也承认某些编程实现的代码可能没有太多不同的写法，你的解答可能与网上其他解答相似。

查看解题提示

本题主要通过 notebook 引导完成，重点在于理解如何将集合覆盖的每个约束翻译成整数线性规划中的线性约束和整数变量。建议先独立完成 notebook 中的概念性检查题，再进入编码部分。

答案状态

本地资料未提供这道题的官方解答；页面只保留题面与非答案式提示。

题面来源：hw11.pdf · 2 · confidence: high