注意:我仍在寻找快速解决方案.下面的两个解决方案是错误的,第三个解决方案非常慢.
我有1个N玩具.... N. 每个玩具都有相关的成本.你必须疯狂购物,在某一天,如果你买玩具我,那么你可以在同一天购买的下一个玩具应该是i + 1或更高.此外,任何两个连续购买的玩具之间的绝对成本差异应大于或等于k.我可以购买所有玩具的最小天数是多少.
我尝试了一种贪婪的方法,首先从玩具1开始,然后看看我可以在第1天购买多少玩具.然后,我找到了我没有买过的最小的i,然后从那里重新开始.
例:
Toys : 1 2 3 4
Cost : 5 4 10 15
设k为5
在第1天,在第2天购买1,3和4,购买玩具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中),但应该快速为您提供参考实现.