1. Integer Linear Programming 1.1. 整数规划 整数规划 (IP) 本质上就是一个带有额外整数约束的线性规划 (LP) 。 我们知道，标准的线性规划处理的是连续变量，比如生产5.25吨的产品，或者投资3.7万元。但在现实世界中，很多决策是不能被分割的，比如你不能雇佣3.5个员工，也不能建造0.7座工厂。整数规划就是为了解决这类问题而生的。 它的通用数学形式如下： $$\begin{array}{rl}\min_{x}&c^\top x\\mathrm{s.t.}&Ax=b,x\geq0\&x_i\in\mathbb{Z},\forall i\…
1.对偶理论 (Duality) 1.1 拉格朗日对偶 (Lagrangian Duality) 为了理解对偶理论，我们先引入拉格朗日函数 (Lagrangian)，它是解决带约束优化问题的一个强大工具。 我们的出发点是一个标准形式的线性规划（LP）问题 。 * 目标: 最小化成本函数 $c^Tx$ 。 * 约束: 解决方案 $x$ 必须满足等式约束 $Ax=b$ 和不等式约束 $x≥0$ 。 为了处理这些约束，我们定义了一个新的函数，即拉格朗日函数 $L(x,y,z)$ ，表达式是 $$L(x,y,z)=c^\top x-y^\top(Ax-b)-z^\top x$$ 这个函数是通过将约束条件融入到原始的目标函数中来构造的 。 在构造过程中，…
1.单纯形算法 (Simplex Algorithm) 1.1 引言：朴素解法的局限性 在线形规划问题中，我们有如下推论： * 可行域 (Feasible Region, Ω): 在几何上，满足约束条件 Ax = b 和 x ≥ 0 的所有解 x 构成的空间是一个凸多面体 (Convex Polyhedron)。你可以把它想象成一个高维度的、由平坦表面围成的几何体。 * 顶点 (Vertex): 就是这个凸多面体的“角点”。 * 为何最优解在顶点上? * 目标函数 c^T x 是线性的。在一个凸多面体内，如果你从一个顶点沿着一条边移动到另一个顶点，目标函数的值要么是线性增加，要么是线性减少，要么保持不变。 * 因此，目标函数的最大值或最小值（最优值）不可能出现在多面体的“内部”或“边”…
机器学习概览 (Machine Learning) 基本概念 机器学习的过程被概括为一个循环流程，包含三个关键环节 ： 1. 数据 (Data)：这是机器学习的基础 。我们假设数据集中隐藏着某种未知的模式或规律。在量化上，它被认为由输入特征和标签 $(s_i,y_i)$ 组成。 2. 模型 (Model)：模型是对数据中隐藏模式的一种简化或数学抽象。它可以是线性的，也可以是非线性的，由一个参数化函数 $h_{x}(s)$ 表示。 3. 优化 (Optimization)：寻找最佳模型的过程，通常被构建为一个优化问题，其被表示成损失函数 + 正则化项 $\min_x\frac{1}{m}\sum_{i=1}^m\ell(y_i,h_x(…
题目 你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。 假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。 返回 多边形进行三角剖分后可以得到的最低分 。 示例 1： 输入：values = [1,2,3] 输出：6 解释：多边形已经三角化，唯一三角形的分数为 6。 示例 2： 输入：values = [3,7,…
类型参数 (泛型) 泛型允许你编写不关心具体类型的函数或数据结构。就像C++的模板一样，你可以写一个 Index 函数，它既能在一个 []int 中查找 int，也能在一个 []string 中查找 string，而无需为每种类型都重写一遍函数。 Go 语言泛型函数: func Index[T comparable](s []T, x T) int 约束 (Constraints)：comparable 的作用 这是Go泛型与传统C++模板（C++20之前）一个非常重要的区别，也是Go泛型设计的核心优势。 * 什么是约束？ 约束（Constraint）是对类型参数 T 的一种“要求”或“规定”。它告诉编译器，任何用来替换 T…
方法 虽然Go没有 class 关键字，但通过为自定义类型（主要是struct）附加方法，它可以实现与C++类非常相似的功能，只是语法和组织方式不同。 对于有C++背景的你来说，理解这一切的关键在于： Go的方法接收者 (Receiver)，在功能上与C++类成员函数中的 this 指针是完全等价的。 1. 语法与定义 我们来详细对比一下定义一个类型和其方法的语法。 C++ 语言: 在C++中，方法（成员函数）的定义是包含在 class 或 struct 的大括号内部的。 #include <iostream> #include <cmath> class Vertex { public: double X, Y; // 方法定义在 class 内部…
指针 Go语言沿用了C/C++中关于指针的两个核心操作符 & 和 *，它们的含义是完全一样的。 * & (取地址操作符 - Address-of Operator) * Go: &i 会生成一个指向变量 i 的指针。 * C++: &i 同样会生成一个指向变量 i 的指针。 * * (解引用操作符 - Dereference Operator) * Go: * 在类型前面，如 *int，表示“一个指向int类型的指针”的类型。 * 在指针变量前面，如 *p，表示获取该指针指向的底层值。 * C++: * 在类型前面，如 int* 或 int *，表示“一个指向int类型的指针”的类型。 * 在指针变量前面，如…