建议最佳算法以找到购买所有玩具的最少天数。

Question

注意：我仍在寻找快速解决方案。以下两个解决方案是错误的，第三个解决方案非常慢。

我有N个玩具，编号从1到N。每个玩具都有一个相关的成本。您必须进行购物狂欢，这样在特定的一天，如果您购买了玩具i，则您可以在同一天购买下一个玩具，该玩具的编号应为i + 1或更高。此外，任何连续购买的两个玩具之间的绝对成本差异应大于或等于k。我最少需要几天才能购买所有玩具？

我尝试了一种贪心方法，首先从玩具1开始，然后看看我可以在第一天买多少个玩具。然后，我找到未购买的最小i并从那里重新开始。

示例：

Toys : 1 2  3  4 
Cost : 5 4 10 15

让 k 为 5

第一天，购买 1、3 和 4 号玩具； 第二天，购买 2 号玩具。

因此，我可以在 2 天内购买所有的玩具。

请注意，贪心算法无法解决以下示例：N = 151，k = 42， 按顺序排列的玩具成本如下：

383 453 942 43 27 308 252 721 926 116 607 200 195 898 568 426 185 604 739 476 354 533 515 244 484 38 734 706 608 136 99 991 589 392 33 615 700 636 687 625 104 293 176 298 542 743 75 726 698 813 201 403 345 715 646 180 105 732 237 712 867 335 54 455 727 439 421 778 426 107 402 529 751 929 178 292 24 253 369 721 65 570 124 762 636 121 941 92 852 178 156 719 864 209 525 942 999 298 719 425 756 472 953 507 401 131 150 424 383 519 496 799 440 971 560 427 92 853 519 295 382 674 365 245 234 890 187 233 539 257 9 294 729 313 152 481 443 302 256 177 820 751 328 611 722 887 37 165 739 555 811

- Zhang Feng

---

你想用什么语言回答？ - austincheney

@austincheney：只要伪代码可行，语言不是问题。我可以轻松编写C、C++、C#、SML、PHP、JS、Java、Scheme。 - Zhang Feng

@austincheney：我更喜欢Java。 - Zhang Feng

我建议你修改最初的免责声明，因为它真的给人一种对着你喊的感觉！不过无论如何，你仍在寻找解决方案，这一事实已经由缺乏被接受的答案表明了！！！ :O - mac

Answer 1

您可以通过解决非对称旅行推销员问题找到最优解。

将每个玩具视为一个节点，并构建完整的有向图（即，在每对节点之间添加一条边）。如果索引较小或目标节点的成本低于源节点的成本加5，则该边具有成本1（必须在第二天继续），否则成本为0。现在查找覆盖此图的最短路径，而不会访问两次节点 - 即解决旅行推销员问题。

这个想法不是很快（它是NP问题），但应该很快给您提供一个参考实现。

- thiton

---

这不会是完整图，因为如果你购买玩具 i，你必须购买玩具 i+1 或更高的。所以，你的解决方案是错误的。 - Zhang Feng

我认为这是正确的解决方案。对于每一对节点A和B，都有两条边，其成本为0和1或1和1。对于从C（当前）到N（下一个）的任何边，只有当N在C之后且abs（value（N）-value（C））> = 5时，成本才为0。 - Dialecticus

@thiton：你提到我们必须找到覆盖这个图的最短路径，而不重复访问节点。然而，根据TSP，起点和终点必须相同。因此，我们必须访问一个节点两次。这是一种矛盾还是我漏掉了什么？ - Zhang Feng

@张峰：没有矛盾，因为您可以任意选择起始节点（毕竟这是一个闭合路径）。选择价格最低的节点作为起始节点，并从闭合路径中删除通往该节点的边缘，以获得覆盖所有节点的开放路径。这是最优的，因为您保证要删除成本为1的边缘（没有办法让该节点继续购物），这也是最高成本。 - thiton

@thiton：你知道有没有地方可以获取 tsp 的可能实现呢？ - Zhang Feng

Answer 2

这不像ATSP那么难。你需要做的就是寻找递增子序列。

作为一名数学家，我解决这个问题的方法是应用RSK来获得一对杨表，然后答案就是杨表的高度和第二个杨表的行告诉你在哪一天购买什么。

思路是在代价序列c上执行Schensted插入。对于你给出的例子c = (5, 4, 10, 15)，插入过程如下：

步骤1：插入c[1] = 5

P = 5

第二步：插入c[2] = 4。

    5
P = 4

步骤3：插入c[3] = 10。

    5
P = 4 10

步骤4：插入c[4] = 15。

    5
P = 4 10 15

想法是将 c 的条目逐个插入 P 中。将 c [i] 插入第 j 行时：

• 如果 c [i] 大于该行中最大的元素，则将其添加到该行的末尾；
• 否则，在第 j 行中找到左侧最靠近的大于 c [i] 的条目，称其为 k ，并用 c [i] 替换 k ，然后将 k 插入到第 j +1 行。

P 是一个数组，其中每行的长度弱下降，并且每行 P 中的条目（这些是成本）弱增加。行数是需要的天数。

对于一个更复杂的示例（通过生成9个随机数字制作）

      1  2  3  4  5  6  7  8  9
c = [ 5  4 16  7 11  4 13  6  5]

     16
      7 
      5  6 11 
P =   4  4  5 13

因此，最佳解决方案需要4天，在第1天购买4件物品，在第2天购买3件物品，在第3天购买1件物品，在第4天购买1件物品。

---

处理连续成本必须至少增加 k 的额外约束需要重新定义成本的（部分）顺序。如果且仅如果在数字的常规排序中 c[j]-c[i] >= k，则认为 c[i] <k< c[j]。上述算法适用于部分顺序和总顺序。

- PengOne

---

我理解你解决方案的第一部分。然而，我不明白如何考虑额外的限制条件，即任意两个连续成本之间的绝对差必须>=k。你能否举一个包含这个限制条件的例子？ - Zhang Feng

还有一件事：要求并不是连续的成本至少应该增加k。要求是连续成本之间的绝对差异应该至少为k。 - Zhang Feng

@张峰 请查看此论文以获取完整细节。 - PengOne

请您能否给我一个包含约束条件的小例子。我时间真的很紧，谢谢。 - Zhang Feng

@张峰：我认为这个解决方案是不正确的，因为它没有考虑到绝对成本差异。它只是说成本应该增加！ - Programmer

@PengOne：错误的解决方案。不符合约束条件。请阅读上面的原因。 - Zhang Feng

Answer 3

我认为采用贪心策略会得到相当不错的结果。

我觉得你的方法不够优化，因为你总是选择玩具1作为起始点，而实际上你应该选择最便宜的玩具。这样做会给你更多移动到下一个玩具的空间。

每一步都采用最便宜的方式，这就是一个 DFS 问题，你需要遵循代价最小的路径并受到 k 的限制。

- Jean-Pascal Billaud

---

你的解决方案是错误的。假设玩具分别为1、2、3和4，它们的成本分别为5、4、3、2。根据你的解决方案，我需要花费4天，因为我会在第一天购买最便宜的玩具4，以此类推。然而，根据我的解决方案，如果我从玩具1开始购买，我只需要花费1天。 - Zhang Feng

你说得对。其实我错误地认为Matroid可以在这里应用。我错过了下一个选择中有一些排序的事实... - Jean-Pascal Billaud