做法
将订单按利润降序排列,将货车按载货量升序排列。从前往后枚举每一个订单,对于当前订单,从前往后找到第一辆未使用且能容纳它的货车运输。
证明
- 若贪心解中当前订单找不到满足条件的货车,则任意一个最优解都可以不选择它。首先,对于任意一个包含该订单的最优解,该订单使用的货车在贪心解中一定已经被使用,否则贪心解就能找到该货车容纳当前订单。那么,在贪心解中,该货车运输的订单利润一定大于等于当前订单,此时让最优解中的这辆货车从运输当前订单,改为运输它在贪心解中匹配的订单,利润不会变小,因此最优解可以不选择当前订单。
- 若贪心解中当前订单可以找到满足条件的货车,则任意一个最优解都可以选择它。首先,对于任意一个没有选择当前订单的最优解,贪心解中与当前订单匹配的货车在最优解中一定匹配了其它订单,否则该货车是空闲的,让它运输当前订单能使利润更大,这与最优解利润最大矛盾。其次,该货车一定匹配了利润大于等于当前订单的订单,否则让它匹配当前订单能使利润更大,这与最优解利润最大矛盾。那么,
- 若该货车匹配的订单利润等于当前订单,则让它匹配当前订单利润不变,仍是最优解。
- 若该货车匹配的订单利润大于当前订单,则在贪心解中,那个订单一定已经被选择且匹配的货车载重量一定小于等于当前货车。原因如下:贪心解中利润更大的订单会被优先考虑,由最优解可知,当前货车载重量大于等于该利润更大的订单的重量,如果不存在载重量小于等于当前货车且能容纳该利润更大的订单的货车,当前货车就会被选择,这与当前货车空闲矛盾。下图中,红线是最优解匹配,黑线是贪心解匹配。记当前订单为 Pi,贪心解中与其匹配的货车是 Ri,最优解中 Ri 匹配 Pj,贪心解中 Pj 匹配 Rj。
- 情况一,最优解中货车 Rj 匹配订单 Pk,满足 Pi≥Pk。此时,对于 Ri,Rj 这两辆货车,贪心解和最优解都要使用,但贪心解利润不比最优解差,因此当前订单 Pi 可以被最优解选择。注意,Rj 在最优解中可能是空闲的,此时只需认为它匹配了一个重量和利润都为 0 的订单 Pk。
- 情况二,最优解中货车 Rj 匹配订单 Pk,满足 Pi<Pk。由于上述相同原因,贪心解也包含 Pk,且匹配的货车载重量一定小于等于 Ri,假设它是 Rk。继续考虑最优解中 Rk 匹配的订单 Pu,只要 Pu 大于 Pi,贪心解就会包含它。以此类推,由于订单数有限,以上过程一定能结束。若在此过程中,出现一个利润小于等于 Pi 的订单(或出现一辆货车,它在贪心解中被使用,而在最优解中空闲,只需认为在最优解中它匹配了一个重量和利润都为 0 的订单),此时用 Pi 代替它结果不会变差(遍历过程中,贪心解和最优解使用的货车集合相同),因此最优解可以包含 Pi。若找到的所有订单利润都大于 Pi,则贪心解不仅全部包含这些订单,而且对于每一个订单,贪心解使用的货车载重量都小于等于最优解里使用的货车。因此,只要将最优解运输这些订单使用的货车集合,改为使用贪心解里的相应集合,不仅利润不会变小,也能包含当前订单 Pi。
综上,贪心解就是一个最优解。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using Plan = vector<pair<int, int>>;
const int N = 1010;
int n, k;
bool st[N];
struct O {
int c, p, id;
bool operator<(const O& rhs) const { return p > rhs.p; }
} ords[N];
struct C {
int r, id;
bool operator<(const C& rhs) const { return r < rhs.r; }
} cars[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
auto& [c, p, id] = ords[i];
scanf("%d%d", &c, &p);
id = i;
}
scanf("%d", &k);
for (int i = 1; i <= k; i++) {
auto& [r, id] = cars[i];
scanf("%d", &r);
id = i;
}
sort(ords + 1, ords + 1 + n);
sort(cars + 1, cars + 1 + k);
Plan pl;
int sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
if (!st[j] && cars[j].r >= ords[i].c) {
st[j] = true;
pl.push_back({ords[i].id, cars[j].id});
sum += ords[i].p;
break;
}
printf("%d %d\n", pl.size(), sum);
for (const auto& [oid, cid]: pl)
printf("%d %d\n", oid, cid);
return 0;
}
代码太优雅了
。