贪心算法方法
所以我有这个问题，一个只有 1 个送货员的食品店必须向顾客提供食品。早上所有的订单都收到了，中午他就开始发货了。每个顾客i都有ti（准备和交付食物的时间）和vi（对食物地点的重要性）。因此，如果客户j是第一个客户，他的订单将在Xj = tj时间内交付。如果客户的f食物在客户j之后准备好并交付，则他的食物将在Xf = Xj + tf时间内交付。关于重要性因素，送货员的目标是使迟到的总和最小，其中迟到是： sum from i=1 to 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 first: c1_sum = d1 * i1 + (d1 + d2) * i2 = d1 * i1 + d1 * i2 + d2 * i2
c2 first:c2_sum = d2 * i2 + (d1 + d2) * i1 = d2 * i2 + d1 * i1 + d2 * i1
d1 * i1出现在两个和中。对于d2 * i2. 唯一的区别是d1 * i2vs d2 * i1。这意味着c1_sum < c2_sum <=> d1 * i2 < d2 * i1。
走向解决方案：
现在让我们考虑具有多个客户 c1, ... cn 的原始任务。如果对于每个其他客户cl (l=0..n, l != k)这是真的，那么客户ck应该具有优先权：dk * il < dl * ik。
这是为什么？
对于一个客户来说，唯一重要的是他自己的时间*重要性分数是固定的前客户的时间总和。因此，我们将要比较我们将保留其他客户与保留该单个客户的程度。
我们是否必须在每一步都重新计算所有内容？
如果在每一步，我们都必须为每对元素计算这个比较，我们将处于 O(n 3 )不太好的领域。多项式复杂度是可以管理的，但是指数中的 3 很烦人，如果我们能阻止它，那就最好了。例如通过对节点进行排序。1我们能做到吗？
- 反射性：保持。
- 反对称性：如果dk * il = dl * ik这意味着dk * il < dl * ik等价于(dk / ik) < (dl / il)
- 传递性类似于上一步。
注意：感谢@?????????，我忘记了这个部门的存在，并且在索引中有点纠结。
所以由于关系是一个顺序，我们可以按它排序。排序是 O(n log(n)) 然后我们可以按顺序贪婪地抓取碎片。
1按距离/重要性比。