Suggest optimal algorithm to find min number of days to purchase all toys

Question

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

Answer 1

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.