最大切分乘积#

LeetCode: 343. 整数拆分 给定一个正整数 $n$ ，将其切分为 $k$ 个正整数的和 ($k \ge 2$)，求切分后所有整数的乘积的最大值是多少。

解：

设将数 $n$ 切分为 $k$ 个正整数 $n_1, n_2, \ldots, n_k$ 的和，记为

目标是最大化

根据均值不等式

等号成立当且仅当 $n_1 = n_2 = \ldots = n_k$ 时成立。因此，为了最大化乘积 $P$，我们应尽量使各个切分的整数相等。

假设将 $n$ 用 $x$ 为因子等分成 $k$ 份，即 $n = kx$，则乘积为

为了最大化 $f(x)$，直接对 $g(x) = \frac{1}{x} \ln x$ 求导

显然，当 $x = e$ 时，$g'(x) = 0$，函数 $g(x)$ 在 $x = e$ 处取得最大值。

考虑到切分因子必须为整数，我们选择最接近 $e$ 的整数，即 $2$ 和 $3$。通过比较可以发现，使用 $3$ 作为切分因子通常能获得更大的乘积。

因此，贪心策略为

• 尽可能多地使用 $3$ 进行切分。
• 当剩余部分为 $2$ 时 ($n \text{ mod } 3 = 2$)，直接使用 $2$。
• 当剩余部分为 $1$ 时 ($n \text{ mod } 3 = 1$)，将一个 $3$ 与这个 $1$ 合并然后拆分为 $2 + 2$，因为 $3 \times 1 < 2 \times 2$。

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) return n - 1;
        int prod = 1;
        while (n > 4) {
            // 当 n % 3 == 1 时，循环最终会停在 n == 4
            // 此时不再拆分 3，而是直接乘以 4
            // 符合下面的代码
            prod *= 3;
            n -= 3;
        } 
        prod *= n;
        return prod;
    }
};

// 或者直接使用数学公式
class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if (b == 0) return pow(3, a);
        if (b == 1) return pow(3, a - 1) * 4;
        return pow(3, a) * 2;
    }
};

分数背包#

给定 $n$ 个物品，和一个容量为 $capacity$ 的背包。其中第 $i$ 个物品的重量为 $weight[𝑖 − 1]$，价值为 $value[𝑖 − 1]$。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，求在限定背包容量下背包中物品的最大价值。

注意这里是分数背包，即每个物品不用全部装入背包，可以选择部分装入。例如，面前有 10kg 的黄金，5kg 的白银，背包容量为 7kg，可以选择装入 5kg 黄金和 2kg 白银（分别是原有黄金和白银的 1/2 和 2/5）。

解:

考虑使用最大化单位重量下的物品价值的贪心策略。由于是分数背包，因此这样的贪心选择必然是最优的。

double fracKnapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<pair<double, int>> vp; // (value/weight, index)
    for (int i = 0; i < n; i++) {
        vp.push_back({(double)values[i] / weights[i], i});
    }
    sort(vp.rbegin(), vp.rend()); // 按照单位重量价值从大到小排序
    double totalValue = 0.0;
    for (const auto& [ratio, idx] : vp) {
        if (capacity <= 0) break;
        int takeWeight = min(capacity, weights[idx]);
        totalValue += takeWeight * ratio;
        capacity -= takeWeight;
    }
    return totalValue;
}

最大容量问题#

LeetCode: 11. 盛最多水的容器 输入一个长度为 $n$ 的数组 $height$，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。容器的容量等于所围成的面积大小。求如何在数组中选择两个隔板，使得组成的容器的容量最大。返回最大容量。

解:

这题自然可以用穷举求解，但是采用贪心法可以缩小搜索空间。

使用左右双指针，左指针 $left$ 指向数组开头，右指针 $right$ 指向数组结尾。计算当前容器的容量，并更新最大容量。然后每次向内移动较短的指针，直至两个指针相遇。在这个过程中记录最大容量。

这里每次移动的是较短的指针，是因为如果移动较长的指针，容量必定是不会增加的（因为容器的有效高度由短板决定，移动长板不会增加短板的高度，只会减少宽度）。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int max_vol = 0;
        while (left < right) {
            int vol = min(height[left], height[right]) * (right - left);
            max_vol = max(max_vol, vol);
            if (height[left] > height[right]) right--;
            else left++;
        }
        return max_vol;
    }
};

活动选择问题 (多区间调度问题)#

• LeetCode: 435. 无重叠区间
• LeetCode: 646. 最长数对链

给定若干半开区间 $[s_i, f_i)$，选出最多个互不重叠的区间。

解:

• 将区间按结束时间 $f$ 升序排序。
• 依次扫描，若当前区间的开始时间 $s \geq last\_end$，则选择该区间，并更新 $last\_end = f$。
• 该策略同时用于 435/646；时间复杂度 $O(n \log n)$（排序）。

正确性要点

• 贪心选择性质：最早结束的区间留给后续最多的可用时间。
• 最优子结构：选择最早结束的区间后，剩余问题在右侧子区间上同样最优。

// 435. 无重叠区间：返回最少删除数
class Solution435 {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(),
             [](const auto& a, const auto& b){ return a[1] < b[1]; });
        int cnt = 0, lastEnd = INT_MIN;
        for (auto& it : intervals) {
            if (it[0] >= lastEnd) { // 选
                cnt++;
                lastEnd = it[1];
            }
        }
        return (int)intervals.size() - cnt; // 删除 = 总数 - 可选最大数
    }
};

// 646. 最长数对链：返回可选最大数
class Solution646 {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(),
             [](const auto& a, const auto& b){ return a[1] < b[1]; });
        int cnt = 0, lastEnd = INT_MIN;
        for (auto& p : pairs) {
            if (p[0] >= lastEnd) { // 选
                cnt++;
                lastEnd = p[1];
            }
        }
        return cnt;
    }
};

其他经典的贪心算法#

• Huffman 编码：用于数据压缩，通过构建最优前缀码树来最小化编码长度。
• Prim 和 Kruskal 算法：用于寻找加权无向图的最小生成树。
• Dijkstra 算法：用于寻找加权有向图中单源最短路径。

逐步坐标下降优化#

假设我们有一个标量值函数 $f(x), x \in \mathbb{R}^n$，$n$ 是一个非常大的数。我们想要找到 $f(x)$ 的最小值。假设这里我们不能使用梯度下降法，因为计算梯度涉及到非常复杂的微分计算，难以快速得到梯度信息（或者压根就是不可微的一个函数）。

我们考虑一种简单的贪心策略：逐步坐标下降（Coordinate Descent）。这种方法的核心思想是每次只优化一个变量，保持其他变量不变。

逐步坐标下降算法

很显然，这种贪心的方法并不能保证全局最优解，但在某些情况下，它可以快速找到一个较好的局部最优解。

可以证明，当满足 $f(x)$ 是凸函数时，逐步坐标下降法能够收敛到全局最优解。

证明:

设 $x^*$ 是 $f(x)$ 的全局最优解，$x^{(k)}$ 是第 $k$ 次迭代的解。根据逐步坐标下降法的定义，我们有： $f(x^{(k+1)}) \leq f(x^{(k)})$ 因为每次迭代都选择了当前坐标的最优值。

由于 $f(x)$ 是凸函数，且 $f(x)$ 在每次迭代中单调递减且有下界（因为 $f(x)$ 有最小值），根据单调有界定理，序列 $\{f(x^{(k)})\}$ 收敛。

考虑到凸函数有且只有一个最小值，因此，逐步坐标下降法在 $f(x)$ 是凸函数的条件下，能够收敛到全局最优解。

问题: 如果函数 $f(x)$ 不是凸函数呢？

在这种情况下，逐步坐标下降法可能会陷入局部最优解，无法保证找到全局最优解。这是因为非凸函数具有不止一个的极小值点。由上述迭代情况的分析，坐标下降法可以收敛到不同的局部最优解，具体取决于初始点 $x^{(0)}$ 的选择。这说明了贪心策略在非凸优化问题或其他优化问题中的局限性。