贪心算法
Greedy Algorithm Approach
所以我遇到了这个问题，一个只有 1 名送货员的食品店必须向顾客送餐。它在早上收到所有订单，中午他将开始发货。每个顾客 i 有 ti（准备和送餐的时间）和 vi（对食物的地方）。因此，如果客户 j 是第一个客户，他的订单将及时交付 Xj = tj。如果顾客f的食物在顾客j之后准备好并送达，他的食物将及时送达Xf = Xj + tf。关于重要性因素，送货员的目标是使迟到总和最少，其中迟到是：总和从i=1到n（其中n个客户）vi * Xi.
例如：
我有这份客户名单
CUSTOMER DISTANCE IMPORTANCE
1 10 8
2 1 8
3 5 7
4 5 3
5 3 7
如果我将它们按每次交付给最近的客户进行排序，而不考虑他的重要性，我将得到以下总和：
（如果2个距离相同则选择最重要的一个）
The sum by distance is :333
(8*1+7*4+7*9+3*14+8*24 = 333)
这将是交货顺序
CUSTOMER DISTANCE IMPORTANCE
2 1 8
5 3 7
3 5 7
4 5 3
1 10 8
我也试过每次选择最重要的客户，总和为：
（如果2个重要性相同则选择距离最小的一个）
The sum by importance is :399
(8*1+8*11+7*14+7*19+3*24 = 399)
以及交货顺序：
CUSTOMER DISTANCE IMPORTANCE
2 1 8
1 10 8
5 3 7
3 5 7
4 5 3
所以在这种情况下，始终选择最接近的一个计算的总和确实比选择始终最重要的一个计算的总和小，但这并不是每次都有效。我必须想出一些能在每个给定列表中给我最佳总和的东西。我知道必须同时考虑距离和重要性，但我无法弄清楚我必须应用的公式才能始终获得最少的总和。如果有人知道将在这种情况下使用的任何贪婪算法技术，我将不胜感激。谢谢。
注意：您提到的两种贪婪方法都不会产生最优解。
看这个顺序：
CUSTOMER DISTANCE IMPORTANCE
2 1 8
5 3 7
3 5 7
1 10 8
4 5 3
结果总和为 323。发生这种情况是因为 10 * 3 = 30 < 40 = 5 * 8。
问题变成了：我们能否在此观察的基础上进行构建？
从简单开始：
让我们看一下只有两个客户的情况：
c1 d1 i1
c2 d2 i2
如果我们先取 c1，它的 成本 将是 d1 * i1。同时，他会将后续每个客户cx的成本增加cx * d1。对于客户 c2，反之亦然。那我们先选哪个呢？
c1 第一：c1_sum = d1 * i1 + (d1 + d2) * i2 = d1 * i1 + d1 * i2 + d2 * i2
c2 第一：c2_sum = d2 * i2 + (d1 + d2) * i1 = d2 * i2 + d1 * i1 + d2 * i1
d1 * i1 出现在两个总和中。 d2 * i2 也一样。唯一的区别是 d1 * i2 与 d2 * i1。这意味着 c1_sum < c2_sum <=> d1 * i2 < d2 * i1.
走向解决方案：
现在让我们考虑具有多个客户 c1, ... cn 的原始任务。如果对于所有其他客户 cl (l=0..n, l != k)，客户 ck 应该具有优先权：dk * il < dl * ik.
这是为什么？
对于一个客户来说，唯一重要的是自从他自己的时间以来前面的客户的次数总和*重要性分数是固定的。因此，我们将要比较我们将保留其他客户的程度，而不是保留单个客户的程度。
我们是否必须在每一步都重新计算所有内容？
如果在每一步，我们都必须为每对元素计算这种比较，我们将处于 O(n3) 的不太好的区域。多项式的复杂性是可以控制的，但是指数中的 3 是相当烦人的，如果我们能阻止它，那将是最好的。例如通过对节点进行排序。1 我们可以这样做吗？
- 自反性： 成立。
- 反对称：如果dk * il = dl * ik表示dk * il < dl * ik 相当于 (dk / ik) < (dl / il)
- 传递性 与上一步类似。
注意： 感谢@รยקคгรђשค，我忘记了该部门的存在并且在索引中有点纠结。
因为关系是一个顺序，所以我们可以按它排序。排序是O(n log(n)) 然后我们可以贪婪地按顺序抓取碎片。
1按距离/重要性比。
所以我遇到了这个问题，一个只有 1 名送货员的食品店必须向顾客送餐。它在早上收到所有订单，中午他将开始发货。每个顾客 i 有 ti（准备和送餐的时间）和 vi（对食物的地方）。因此，如果客户 j 是第一个客户，他的订单将及时交付 Xj = tj。如果顾客f的食物在顾客j之后准备好并送达，他的食物将及时送达Xf = Xj + tf。关于重要性因素，送货员的目标是使迟到总和最少，其中迟到是：总和从i=1到n（其中n个客户）vi * Xi.
例如：
我有这份客户名单
CUSTOMER DISTANCE IMPORTANCE
1 10 8
2 1 8
3 5 7
4 5 3
5 3 7
如果我将它们按每次交付给最近的客户进行排序，而不考虑他的重要性，我将得到以下总和：
（如果2个距离相同则选择最重要的一个）
The sum by distance is :333
(8*1+7*4+7*9+3*14+8*24 = 333)
这将是交货顺序
CUSTOMER DISTANCE IMPORTANCE
2 1 8
5 3 7
3 5 7
4 5 3
1 10 8
我也试过每次选择最重要的客户，总和为：
（如果2个重要性相同则选择距离最小的一个）
The sum by importance is :399
(8*1+8*11+7*14+7*19+3*24 = 399)
以及交货顺序：
CUSTOMER DISTANCE IMPORTANCE
2 1 8
1 10 8
5 3 7
3 5 7
4 5 3
所以在这种情况下，始终选择最接近的一个计算的总和确实比选择始终最重要的一个计算的总和小，但这并不是每次都有效。我必须想出一些能在每个给定列表中给我最佳总和的东西。我知道必须同时考虑距离和重要性，但我无法弄清楚我必须应用的公式才能始终获得最少的总和。如果有人知道将在这种情况下使用的任何贪婪算法技术，我将不胜感激。谢谢。
注意：您提到的两种贪婪方法都不会产生最优解。
看这个顺序：
CUSTOMER DISTANCE IMPORTANCE
2 1 8
5 3 7
3 5 7
1 10 8
4 5 3
结果总和为 323。发生这种情况是因为 10 * 3 = 30 < 40 = 5 * 8。
问题变成了：我们能否在此观察的基础上进行构建？
从简单开始：
让我们看一下只有两个客户的情况：
c1 d1 i1
c2 d2 i2
如果我们先取 c1，它的 成本 将是 d1 * i1。同时，他会将后续每个客户cx的成本增加cx * d1。对于客户 c2，反之亦然。那我们先选哪个呢？
c1 第一：c1_sum = d1 * i1 + (d1 + d2) * i2 = d1 * i1 + d1 * i2 + d2 * i2
c2 第一：c2_sum = d2 * i2 + (d1 + d2) * i1 = d2 * i2 + d1 * i1 + d2 * i1
d1 * i1 出现在两个总和中。 d2 * i2 也一样。唯一的区别是 d1 * i2 与 d2 * i1。这意味着 c1_sum < c2_sum <=> d1 * i2 < d2 * i1.
走向解决方案：
现在让我们考虑具有多个客户 c1, ... cn 的原始任务。如果对于所有其他客户 cl (l=0..n, l != k)，客户 ck 应该具有优先权：dk * il < dl * ik.
这是为什么？
对于一个客户来说，唯一重要的是自从他自己的时间以来前面的客户的次数总和*重要性分数是固定的。因此，我们将要比较我们将保留其他客户的程度，而不是保留单个客户的程度。
我们是否必须在每一步都重新计算所有内容？
如果在每一步，我们都必须为每对元素计算这种比较，我们将处于 O(n3) 的不太好的区域。多项式的复杂性是可以控制的，但是指数中的 3 是相当烦人的，如果我们能阻止它，那将是最好的。例如通过对节点进行排序。1 我们可以这样做吗？
- 自反性： 成立。
- 反对称：如果dk * il = dl * ik表示dk * il < dl * ik 相当于 (dk / ik) < (dl / il)
- 传递性 与上一步类似。
注意： 感谢@รยקคгรђשค，我忘记了该部门的存在并且在索引中有点纠结。
因为关系是一个顺序，所以我们可以按它排序。排序是O(n log(n)) 然后我们可以贪婪地按顺序抓取碎片。
1按距离/重要性比。