Visiting a supermarket with a shopping list, get all items in the fastest way?
Once in a while, my wife sends me to a REAL supermarket, with a shopping list (she writes me an a piece of paper, or texts me a message).
I was wondering is there a fast way to for-fill the list, without iterating the whole super a dozens of times, till I believe I've got everything.
(I found this question very helpful in life: pair-socks-from-a-pile-efficiently, and hoped I can use the community's help in my own situation)
I don't know/remember where each item is located in the supermarket, and the list I'm given is never sorted (for example, vegetables are listed all over the list, and not one after the other). Also, usually I get continuously text messages with more and more items to buy, while I'm still in the super.
My approach is planning a path that would assure me I iterate the whole supermarket, and pick items from the list while walking that path.
Two ways I was thinking about:
(n)
I pass: check if I have such item in my list (m) , will give me an O(n*m)
complicity, which not so efficient. (p)
: standing on the beginning of each row I can read the sign or see which sort of items I should find there, than iterate my list, trying to remember all items in list I should find in that row. than walk that row and add those items to my cart, should give me O(p*m)
complicity. but this never really happens : I can't remember more than three of four items from my list I'm expecting to find in that row, and even if I do, I often forget an item and have to use this algorithm again (lets say q
times) , which comes to: O(q*p*m)
. A couple of comments I'd like to add:
(v)
. Sure I can't remember all those veggies, and rather not stop next to each vegetable in the market (or should I?), to check if I've got it in my list. Looking up rearrangement time here, my initial idea of putting in the time to map you usual items would be useless. (they re arrange aisles pretty often).
For any ideas going down that road - not going to work...
链接地址: http://www.djcxy.com/p/12202.html