注意:我仍然在寻找一个快速的解决方案。下面的两个解决方案是错误的，第三个解决方案非常慢。
我有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
因此，我可以在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
可以通过求解不对称旅行推销员问题找到最优解。
将每个玩具视为一个节点，构建完全有向图(即在每对节点之间添加一条边)。如果索引更小，或者目标节点的成本小于5加上源节点的成本，那么这条边的成本为1(必须在第二天继续)，否则为0。现在找到覆盖这个图的最短路径，而不需要访问一个节点两次——即，解决旅行推销员问题。
这个想法不是很快(它在NP中)，但应该很快给你一个参考实现。
这并不像ATSP那么困难。你所需要做的就是寻找递增的子序列。
作为一个数学家，我解决这个问题的方法是应用RSK来获得一对Young的表格，然后多少天的答案是表格的高度和第二张表格的行告诉你在哪一天买什么。
思路是在代价序列c上进行Schensted插入。对于您给出的示例c = (5, 4, 10, 15)，插入是这样的:
c[1] = 5
P = 5
步骤2:插入c[2] = 4
5
P = 4
步骤3:插入c[3] = 10
5
P = 4 10
c[4] = 15
5
P = 4 10 15
的想法是，你插入c的条目到P一次一个。当c[i]插入j行:
- 如果
c[i]大于行中最大的元素，则将其添加到行尾; - 否则，在
j行中找到比c[i]大的最左边的条目，称其为k，将k替换为c[i]，然后将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[i] <k< c[j]当且仅当c[j]-c[i] >= k按通常的数字顺序排列。上述算法既适用于全阶，也适用于偏阶。
我多少觉得贪心的方法会得到一个相当好的结果。
我认为你的方法不是最优的，因为你总是选择玩具1，而你应该选择最便宜的玩具。这样做会给你最大的空间移动到下一个玩具。
每一步都是最便宜的一步，这只是DFS问题，你总是遵循受k约束的最便宜的路径