一类带约束条件的最优选择问题

摘要: 堆贪心解决带约束条件的最优选择问题，放松约束条件使得候选对象越来越多

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在业务场景中，我们经常遇到这样一类优化问题。有一个对象池，其中的每个对象有 x 和 y 两种属性或指标。我们要从中选出若干个对象，使得某个指标最优化。同时另一个指标要满足一些约束条件。

作为目标与作为约束条件的属性或指标，一般是矛盾的。比如指标 x 表示质量、指标 y 表示工时，质量越高越好，工时越低越好。但是一个对象的质量越高，其工时往往也越高：如果按质量越大越好的策略，贪心地选择质量最大的对象，工时可能就会太大；如果按工时越小越好的策略，贪心地选工时最小的对象，那么质量可能就会太小。

实际问题当中，两个有冲突的指标经常把一个放在约束条件中，把一个放在目标函数中。例如上面这组指标，在工时有一个上限的限制下选出若干对象，使得质量最大，这是一个约束优化问题；在质量有一个下限的限制下选出若干对象，使得工时最小，这也是一个约束优化问题。

如果两个指标都是最优化的目标，则为帕累托最优问题，也称为多目标优化，这是另一个问题。比如经济学中的效率和公平就是研究这个问题的。

对象池 -> 候选集 -> 一步选择

更多的时候，我们要做出的最优选择的优化目标是一个指标 x，另一个指标 y 满足约束条件即可。如果随着指标 y 需要满足的条件越来越放松，满足该条件的对象单调增加，那么我们就可以有以下思路。

假设我们要从 N 个对象中进行选择，我们称这原始的 N 个对象构成一个对象池，逐渐放松对指标 y 的要求，将满足要求的对象放进候选集，然后从候选集中选出指标 x 最优的那个对象，该对象即为 y 指标满足当前要求下的最优选择。然后继续放松 y 指标的要求，放一些对象进入候选集，选择 x 最优的对象，直至对象池耗尽。

在不同的问题中，放松 y 指标的过程可能会不一样。下面是两种可能的情况：

• 在满足当前 y 条件的候选集中选出 x 最优的对象后，对 y 条件无影响。此时按 y 指标从小到大的顺序枚举对象池中的 N 个对象即可实现指标 y 逐步放松。题目 826. 安排工作以达到最大收益 是这种情况。
• 在满足当前 y 条件的候选集中选出 x 最优的对象，选择后如果堆 y 条件本身有影响，并且该影响是使得 y 的条件放松，那么不断选择对象，更新影响即可实现指标 y 的逐步放松。 题目 502. IPO 是这种情况。

上述处理过程最大的特点是已经放进候选集中的对象就不会被踢出候选集了，就随着 y 条件不断放松，新对象不断加入的过程始终参选。

本文我们分别讨论上述两种情况下的算法思路，然后解决前面提到的两道题。

问题抽象

将前面的问题描述抽象一下，我们解决的是下面这一类问题。

对象翅中有 N 个对象，一个对象有两种指标 x 和 y，不同的指标和比较策略有矛盾(比如效率和质量)。

从对象池中选出若干个对象，y 指标需要满足约束条件，最优化 x 指标。

每一步都贪心地选择 x 最优的那一个对象，但需要满足：每一步选择都对 y 指标无影响，或者使得 y 指标越来越放松，从而已经进入候选集的对象不会因为一步选择而被踢出去。

与背包问题的对比

此前我们讨论过背包问题，选出的对象的总体积有一个上限，这样的话当我们选出一个对象 item，会占用背包的一些空间，使得背包剩余空间变小，进而造成原本可以选的对象在选了对象 item 之后就不能选了，也就是之前放进候选集中的对象需要被踢出去了。

此时就不能按照前面的不断放松 y 条件，选择 x 最优的一个对象这样的贪心算法了，该问题的解法是一种动态规划算法，参考文章 01背包和完全背包、01背包和完全背包题目汇总。

---

一步选择对约束条件无影响

算法抽象

迭代地进行以下过程，每一轮选出一个对象：

• step1: 根据从对象池进入候选集的筛选条件(约束条件)，从对象池中放出若干个对象进入候选集。
• step2: 根据从候选集选出的筛选条件，从候选集选出一个。

模板问题

有 $M$ 个项目，每个项目有一个难度值 $P[i]$，有 $N$ 个经理，每个经理有一个能力值 $w[i]$，和一个成本值 $v[i]$，一般来说能力值越高，成本值也越高。经理 $j$ 能完成项目 $i$ 的条件是能力值大于等于难度值 $w[j] \geq P[i]$。

选出 $M$ 个经理，使得完成全部 $M$ 个项目的前提下，成本最低。

分析

经理有两个指标：能力和成本，此问题是指标 x (能力) 有约束，最优化指标 y (成本) 的问题。

问题的难点在于，这二者往往是冲突的，不论从哪出发进行贪心都很难证明最优。

对于项目 $i$，其难度为 $P[i]$，要完成该项目，经历的能力值必须不低于 $P[i]$，也就是满足 $w[j] \geq P[i]$ 经理 $j$ 才能作为候选。

将项目按照难度从大到小排序，然后按顺序枚举，解决。当项目难度越来越小，对人员能力的要求越来越低，可以作为候选人员的集合就单调增加。假设当前枚举到项目 $i$，我们在候选集中选择成本最低的经理即可。

826. 安排工作以达到最大收益

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

• difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
• worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

• 举个例子，如果 3 个工人都尝试完成一份报酬为 $\$ 1$ 的同样工作，那么总收益为 $\$ 3$ 。如果一个工人不能完成任何工作，他的收益为 $\$ 0$ 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

提示:

n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 1e4
1 <= difficulty[i], profit[i], worker[i] <= 1e5

示例 1：
输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:
输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

算法：贪心

本题就是我们前面分析的基本问题，算法完全一样。

代码 (C++)

struct Work
{
    int diff;
    int pro;
    Work():diff(-1),pro(-1){}
    Work(int d, int p):diff(d),pro(p){}
};

struct Cmp
{
    bool operator()(const Work& w1, const Work& w2) const
    {
        return w1.diff < w2.diff;
    }
};

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int m = profit.size();
        vector<Work> works(m);
        for(int i = 0; i < m; ++i)
        {
            works[i].diff = difficulty[i];
            works[i].pro = profit[i];
        }
        sort(works.begin(), works.end(), Cmp());
        sort(worker.begin(), worker.end());
        int n = worker.size();
        priority_queue<int> cand_profits;
        int work_iter = 0;
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            while(work_iter < m && works[work_iter].diff <= worker[i])
            {
                cand_profits.push(works[work_iter].pro);
                ++work_iter;
            }
            if(!cand_profits.empty())
                ans += cand_profits.top();
        }
        return ans;
    }
};

---

一步操作可能使得约束条件变松

算法抽象

迭代地进行以下过程，每轮迭代选出一个对象：

• step1: 根据从对象池进入候选集的筛选条件(约束条件)，从对象池中放出若干个对象进入候选集。
• step2: 根据从候选集选出的筛选条件，从候选集选出一个。
• step3: step2选出的对象使得step1的筛选条件放松，更新这个影响。

502. IPO

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

提示：

1 <= k <= 1e5
0 <= w <= 1e9
n == profits.length
n == capital.length
1 <= n <= 1e5
0 <= profits[i] <= 1e4
0 <= capital[i] <= 1e9

示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

算法：贪心

• 对象池是若干个项目

struct Project
{
    int profit;
    int start;
    Project(int p, int s):profit(p),start(s){}
};

• 进入候选集的筛选条件：当前资金(启动资金 <= 当前资金 的项目进入候选集)

struct Cmp
{
    bool operator()(const Project& p1, const Project& p2) const
    {
        return p1.start < p2.start;
    }
};

• 从候选集中被选出的筛选条件: 利润 (选出利润最大的)

struct HeapCmp
{
    bool operator()(const Project& p1, const Project& p2) const
    {
        return p1.profit < p2.profit;
    }
};

• 反馈: 做出当前的选择后，手上的资金会变多，这会使得对象池中可能有新的对象可以进入候选集，同时已经在候选集中的对象不会淘汰出去。也就是说，在选择对象的过程中，约束条件会越来越放松。

代码 (C++)

class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        int n = Profits.size();
        vector<Project> projects;
        for(int i = 0; i < n; ++i)
            projects.emplace_back(Project(Profits[i], Capital[i]));
        sort(projects.begin(), projects.end(), Cmp());
        priority_queue<Project, vector<Project>, HeapCmp> pq;
        int iter = 0;
        while(iter < n && projects[iter].start <= W)
            pq.push(projects[iter++]);
        while(k > 0 && !pq.empty())
        {
            Project choose = pq.top();
            pq.pop();
            int p = choose.profit;
            if(p <= 0)
                return W;
            W += p;
            --k;
            while(iter < n && projects[iter].start <= W)
                pq.push(projects[iter++]);
        }
        return W;
    }
};

---

---