贪心-双指标规划问题

字数统计: 5.4k字 | 阅读时长: 23分

2020-10-01

摘要: 一些用贪心解决的双指标规划问题

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

在业务场景中，我们经常遇到这样一类优化问题。有一个对象池，我们要从中选出 K 个对象。这些对象中，有 x 和 y 两种指标，以及 A 和 B 两种比较策略。例如：

指标 x：质量
指标 y：效率
比较策略 A：质量越大越好
比较策略 B：效率越大越好

但是不同的指标和比较策略往往会有矛盾，比如上面这一组，质量和效率就是矛盾的。如果按策略 A，选择质量最大的对象，那么策略 B 就不满足；如果按策略 B，选效率最大的对象，那么策略 A 就无法满足。

本文我们看一下在这种条件下的各种处理方法，以及实现思路。涉及到力扣 826、502、1642、857、1383、630。根据题目中给出的处理方法的特点，分为择优型、择优并反馈型、淘汰型问题。以下是总览：

$0 问题抽象

从对象池中选出最优的 1 个或 K 个对象。

一个对象有两种指标及其比较策略 A 和 B，不同的指标和比较策略有矛盾(比如效率和质量)。

在这样的条件下解决一些这样一类问题：约束和目标与 A 和 B 相关，从对象池中选出最优的若干对象。

$1 择优型问题

算法抽象

迭代最终选择的对象，每轮迭代的过程：

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

模板问题

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

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

分析

经理有两个指标：能力和成本，能力是抽象问题中的指标 A，成本是抽象问题中的指标 B，此问题是 A 有约束，最优化 B 的问题

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

合理的贪心策略：

1
2

对于项目难度值(能力值要求)从大向小排序，枚举项目，当前枚举到 i，
    总在剩余的满足当前能力值要求(能力值大于等于难度值 `P[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;
    }
};

$2 择优并反馈型问题

算法抽象

迭代最终选择的对象，每轮迭代的过程：

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 Sort_cmp
{
    bool operator()(const Project& p1, const Project& p2) const
    {
        return p1.start < p2.start;
    }
};

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

struct Heap_cmp
{
    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(), Sort_cmp());
        priority_queue<Project, vector<Project>, Heap_cmp> 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;
    }
};

1642. 可以到达的最远建筑

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标从 0 开始）时：

如果当前建筑物的高度大于或等于下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度小于下一个建筑的高度，您可以使用一架梯子或 (h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标从 0 开始）。

提示：

1 <= heights.length <= 1e5
1 <= heights[i] <= 1e6
0 <= bricks <= 1e9
0 <= ladders <= heights.length

示例 1：
输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：

不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2

使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7

不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6

使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。
示例 2：

输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出：7
示例 3：

输入：heights = [14,3,19,3], bricks = 17, ladders = 0
输出：3

算法：贪心

将当前高度差压堆，优先使用梯子，体积不够就取最短的高度差换为用砖块，砖块不够则无法前进。

代码 (C++)

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int n = heights.size();
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 0; i < n - 1; ++i)
        {
            int diff = heights[i + 1] - heights[i];
            if(diff <= 0)
                continue;
            if(ladders > 0)
            {
                --ladders;
                pq.push(diff);
            }
            else
            {
                pq.push(diff);
                if(pq.top() <= bricks)
                {
                    bricks -= pq.top();
                    pq.pop();
                }
                else
                    return i;
            }
        }
        return n - 1;
    }
};

$3 淘汰型问题

算法抽象

迭代对象池中的对象，每轮迭代的过程：

step1: 根据从对象池进入候选集的筛选条件(参选条件)，从对象池中放出一个对象进入候选集
step2: 根据从候选集淘汰的筛选条件，如果有必要，则从候选集淘汰一个

当对象池的对象迭代完，留在候选集中的就是最终选择的。

857. 雇佣 K 名工人的最低成本

有 n 名工人。给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个工资组。在雇佣一组 k 名工人时，我们必须按照下述规则向他们支付工资：

对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ，返回组成满足上述条件的付费群体所需的最小金额。在实际答案的 10-5 以内的答案将被接受。。

提示：

1
2
3

n == quality.length == wage.length
1 <= k <= n <= 1e4
1 <= quality[i], wage[i] <= 1e4

示例 1：
输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释：我们向 0 号工人支付 70，向 2 号工人支付 35。

示例 2：
输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
输出： 30.66667
解释：我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。

算法：贪心

K 个人分别是 $i_{1}, i_{2}, …, i_{K}$

总工资 = $(q[i_{1}] + q[i_{2}] + … + q[i_{k}]) * x$

x 为常数且为 w[i] / q[i] 之一

若 i 选了，则 x[i] >= w[i] / q[i]

因此随着 w[i] / q[i] 越来越大，满足的候选越来越多

若选定了 x，即当前枚举到的 x(当前所有后选中最大)，选择所有候选中 q 最小的 k 个

对象池是 N 名工人

struct Worker
{
    int q, w;
    Worker(int q, int w):q(q),w(w){}
};

进入候选集的筛选条件：性价比(这一步比较难，需要前面的推导)

struct Sort_cmp
{
    // 按 w[i] / q[i] 从大到小排序
    bool operator()(const Worker& worker1, const Worker& worker2) const
    {
        return (double)worker1.w / worker1.q < (double)worker2.w / worker2.q;
    }
};

从候选集中淘汰的筛选条件：成本(保留成本最小的 K 个)

struct Heap_cmp
{
    bool operator()(const Worker& worker1, const Worker& worker2) const
    {
        return worker1.q < worker2.q;
    }
};

代码 (C++)

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
        int n = quality.size();
        vector<Worker> workers;
        for(int i = 0; i < n; ++i)
            workers.emplace_back(quality[i], wage[i]);
        sort(workers.begin(), workers.end(), Sort_cmp());
        priority_queue<Worker, vector<Worker>, Heap_cmp> pq;
        int sum_q = 0;
        for(int i = 0; i < K; ++i)
        {
            sum_q += workers[i].q;
            pq.push(workers[i]);
        }
        // x 的初始值为 (double)workers[K - 1].w / workers[K - 1].q
        double result = sum_q * (double)workers[K - 1].w / workers[K - 1].q;
        for(int i = K; i < n; ++i)
        {
            if(pq.top().q > workers[i].q)
            {
                sum_q -= pq.top().q;
                pq.pop();
                pq.push(workers[i]);
                sum_q += workers[i].q;
                result = min(result, sum_q * (double)workers[i].w / workers[i].q);
            }
        }
        return result;
    }
};

1383. 最大的团队表现值

公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。

团队表现值的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

提示：

1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n

示例 1：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出：60
解释：
我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。

示例 2：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出：68
解释：
此示例与第一个示例相同，除了 k = 3 。我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。

示例 3：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出：72

算法：贪心

题解参考：力扣1383-最大的团队表现值

最优化速度和和效率最小值的乘积。变化的量有两个，一个是速度，一个是效率。不妨采用动一个，定一个的策略

当固定 efficiency 时候，目标是从满足条件的 speed 中选择最大的 k 个，其中只要工程师的 efficiency 不小于当前枚举的 efficiency 时即满足条件。

对象池是 N 个工程师

struct Engineer
{
    int speed, efficiency;
    Engineer(int s, int e):speed(s),efficiency(e){}
};

进入候选集的筛选条件，效率需要大于当前枚举值

struct Cmp
{
    bool operator()(const Engineer& engineer1, const Engineer& engineer2)
    {
        if(engineer1.efficiency == engineer2.efficiency)
            return engineer1.speed > engineer2.speed;
        return engineer1.efficiency > engineer2.efficiency;
    }
};

从候选集中淘汰的筛选条件：速度(保留速度最大的 K 个)

由于是最多选 K 个人而不是恰好选 K 个人，因此堆中不用先初始化好 K 个元素

代码 (C++)

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<Engineer> engineers;
        for(int i = 0; i < n; ++i)
            engineers.push_back(Engineer(speed[i], efficiency[i]));
        sort(engineers.begin(), engineers.end(), Cmp());
        ll result = 0;
        ll sum = 0;
        int min_efficiency = INT_MAX;
        priority_queue<int, vector<int>, greater<int> > pq;
        for(int i = 0; i < n; ++i)
        {
            min_efficiency = min(min_efficiency, engineers[i].efficiency);
            pq.push(engineers[i].speed);
            sum += engineers[i].speed;
            if((int)pq.size() > k)
            {
                sum -= pq.top();
                pq.pop();
            }
            result = max(result, sum * min_efficiency);
        }
        return result % MOD;
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
};

630. 课程表 III

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会持续上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：
输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：
输入：courses = [[1,2]]
输出：1

示例 3：
输入：courses = [[3,2],[4,3]]
输出：0

提示:

1 2	1 <= courses.length <= 1e4 1 <= durationi, lastDayi <= 1e4

算法：贪心

要最大化的是选择的对象个数。

对象池：n 门课

struct Course
{
    int t;
    int d;
    Course(int t, int d):t(t),d(d){}
};

从对象池进入候选集的筛选条件：关闭时间(按照关闭时间从小到大枚举课程)

struct Sort_cmp
{
    bool operator()(const Course& c1, const Course& c2) const
    {
        return c1.d < c2.d;
    }
};

从候选集中淘汰的筛选条件：持续时长

因为要最大化的是选出的对象个数，所以参选的对象(课程关闭时间小于等于当前枚举值)中，保留的课程持续时长越短越好

如果 当前时间 + 持续时长 <= 当前枚举的结束时间，则不需要淘汰

如果 当前时间 + 持续时长 > 当前枚举的结束时间，则需要淘汰一个，淘汰的就是持续时长最长的。

struct Heap_cmp
{
    bool operator()(const Course& c1, const Course& c2) const
    {
        return c1.t > c2.t;
    }
};

代码 (C++)

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        int n = courses.size();
        vector<Course> cs;
        for(int i = 0; i < n; ++i)
            cs.emplace_back(courses[i][0], courses[i][1]);
        sort(cs.begin(), cs.end(), Sort_cmp());
        priority_queue<Course, vector<Course>, Heap_cmp> pq;
        int left = 1;
        for(const Course& c: cs)
        {
            pq.push(c);
            left += c.t;
            if(left - 1 > c.d)
            {
                left -= pq.top().t;
                pq.pop();
            }
        }
        return pq.size();
    }
};

145. 超市

超市里有N件商品，每件商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

算法：贪心

对象池：N 件商品

struct Item
{
    int p;
    int d;
    Item(int p, int d):p(p),d(d){}
};

进入候选集的筛选条件：过期时间(按照过期时间从前到后枚举物品)
从候选集中淘汰的筛选条件：利润

因为要最大化的是利润，所以参选的对象(过期时间小于等于当前枚举值)中，保留的物品利润越大越好

如果 当前时间 <= 当前枚举的结束时间，则不需要淘汰

如果 当前时间 > 当前枚举的结束时间，则需要淘汰一个，淘汰的就是利润最小的。

struct Heap_cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.p > i2.p;
    }
};

代码 (C++)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

struct Item
{
    int p;
    int d;
    Item(int p, int d):p(p),d(d){}
};

struct Sort_cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.d < i2.d;
    }
};

struct Heap_cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.p > i2.p;
    }
};

int main()
{
    int N;
    while(cin >> N)
    {
        vector<Item> items;
        for(int i = 0; i < N; ++i)
        {
            int p, d;
            cin >> p >> d;
            items.emplace_back(p, d);
        }
        sort(items.begin(), items.end(), Sort_cmp());
        priority_queue<Item, vector<Item>, Heap_cmp> pq;
        int left = 0;
        int ans = 0;
        for(const Item& i: items)
        {
            pq.push(i);
            ++left;
            ans += i.p;
            if(left > i.d)
            {
                ans -= pq.top().p;
                pq.pop();
                --left;
            }
        }
        cout << ans << endl;
    }
}

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法基础算法

贪心-双指标规划问题

$0 问题抽象

$1 择优型问题

算法抽象

模板问题

分析

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

算法：贪心

代码 (C++)

$2 择优并反馈型问题

算法抽象

502. IPO

算法：贪心

代码 (C++)

1642. 可以到达的最远建筑

算法：贪心

代码 (C++)

$3 淘汰型问题

算法抽象

857. 雇佣 K 名工人的最低成本

算法：贪心

代码 (C++)

1383. 最大的团队表现值

算法：贪心

代码 (C++)

630. 课程表 III

算法：贪心

代码 (C++)

145. 超市

算法：贪心

代码 (C++)