注意:我仍在寻找一种快速的解决方案。下面的两个解决方案是错误的，而第三个是非常慢的。
我从1..N开始有N个玩具。每个玩具都有相关的成本。您必须疯狂购物，以便在特定的一天，如果您购买玩具i，那么同一天可以购买的下一个玩具应该为i + 1或更大。此外，任何两个连续购买的玩具之间的绝对绝对成本差应大于或等于k。我可以购买所有玩具的最少天数是多少？
我尝试了一种贪婪的方法，首先从玩具1开始，然后看我在第1天可以买多少个玩具。然后，我找到了我没有买的最小的玩具，然后从那里重新开始。
例子:
Toys : 1 2 3 4
Cost : 5 4 10 15
令k为5
在第1天，购买1,3，和4
在第2天，购买玩具2
因此，我可以在2天内购买所有玩具
注意贪婪不适用于以下示例:N = 151和k = 42
玩具1 ... N的价格依次为:
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中)，但是应该很快为您提供引用实现。
关于algorithm - 建议最佳算法以找出购买所有玩具的最少天数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8508338/