建议最佳算法找到最小的天数来购买所有的玩具 [英] Suggest optimal algorithm to find min number of days to purchase all toys
问题描述
注意：我仍然在寻找一个快速的解决方案。下面两个解决方案是错误的，第三个是极其缓慢的。
我有1 .... N N玩具。每个玩具具有与之相关联的成本。你必须去购物US preE，使得在某一天，如果你买的玩具我，那么下一个玩具，你可以在同一天买的应该是我+ 1或更大。此外，在绝对的任何两个连续买玩具的成本差异应大于或等于k。什么是天的最小数，我可以买到所有的玩具。
我尝试了贪婪的方式通过启动玩具1，然后再看到我有多少玩具可以在第1天买。然后，我发现，我没有从那里购买并重新开始最小的我。
例如：
玩具：1 2 3 4
费用：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
您可以通过求解非对称旅行商找到最佳的解决方案。
考虑每个玩具作为一个节点，并建立完整的向图（即，添加的每个节点对之间的边缘）。边缘已经花费1（具有以继续对下一个天）如果指数小于或目标节点的成本小于5加源节点的成本，否则为0。现在找到覆盖这个图没有访问节点两次的最短路径 - 即解决了旅行商
这想法是不是非常快（它是在NP），但应尽快给大家一个参考实现。
Note: I am still looking for a fast solution. Two of the solutions below are wrong and the third one is terribly slow.
I have N toys from 1....N. Each toy has an associated cost with it. You have to go on a shopping spree such that on a particular day, if you buy toy i, then the next toy you can buy on the same day should be i+1 or greater. Moreover, the absolute cost difference between any two consecutively bought toys should be greater than or equal to k. What is the minimum number of days can I buy all the toys.
I tried a greedy approach by starting with toy 1 first and then seeing how many toys can I buy on day 1. Then, I find the smallest i that I have not bought and start again from there.
Example:
Toys : 1 2 3 4
Cost : 5 4 10 15
let k be 5
On day 1, buy 1,3, and 4 on day 2, buy toy 2
Thus, I can buy all toys in 2 days
Note greedy not work for below example: N = 151 and k = 42 the costs of the toys 1...N in that order are :
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
You can find the optimal solution by solving the asymmetric Travelling Salesman.
Consider each toy as a node, and build the complete directed graph (that is, add an edge between each pair of nodes). The edge has cost 1 (has to continue on next day) if the index is smaller or the cost of the target node is less than 5 plus the cost of the source node, and 0 otherwise. Now find the shortest path covering this graph without visiting a node twice - i.e., solve the Travelling Salesman.
This idea is not very fast (it is in NP), but should quickly give you a reference implementation.
这篇关于建议最佳算法找到最小的天数来购买所有的玩具的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
