贪心算法
所以我有一个问题，一个只有一个送货员的快餐店必须给顾客送餐。它有早上的所有订单，中午他将开始送货。每个客户
我
有
时间
(准备和运送食物的时间)和
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如果我通过每次交付给最近的客户来排序，而不考虑他的重要性，我将得到总和：
(如果两个具有相同的距离，则选择最重要的一个)
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我还试着每次选择最重要的客户，总和是：
(如果两个具有相同的重要性，则选择距离最小的一个)
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因此，在这种情况下，总是选择最接近的一个确实比选择总是最重要的一个计算出的和更小，但这并不是每次都有效。我必须想出一些东西，让我在每个给定的列表中都能得到最优的总和。我知道必须同时考虑距离和重要性，但我想不出我必须应用什么公式才能始终获得最小和。如果有人知道在此场景中将使用的任何贪婪算法技术，我将不胜感激。谢谢。
回答 1
Stack Overflow用户
发布于 2021-03-01 19:46:51
注意：
您提到的两种贪婪方法都不会产生最佳解决方案。
看看这个命令：
CUSTOMER DISTANCE IMPORTANCE
2 1 8
5 3 7
3 5 7
1 10 8
4 5 3得到的总和是323。发生这种情况是因为
..。
问题变成了:我们可以在这个观察的基础上构建吗？
从简单的开始：
让我们看一下只有两个客户的情况：
c1 d1 i1
c2 d2 i2如果我们先使用c1，它的
成本
将会是
..。同时，他将增加每个后续客户的成本
cx
由
..。客户c2也是如此。那我们先选哪一个呢？
c1优先：
c2优先：
出现在两个和数中。相同的
..。唯一的区别是
vs
..。这意味着
c1
_
sum < c2
_
总和
<=>
d1
*
i2 < d2
*
i1
..。
迈向解决方案：
现在让我们考虑具有多个客户的原始任务c1，...cn.客户
确认
如果每个其他客户都有优先权，则应优先考虑
cl (l=0..n，l != k)
这是真的：
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由
距离/重要性
比率。
https://stackoverflow.com/questions/66420136
复制相似问题
腾讯云开发者
