CODEWITHSUNDEEP
algorithm
ripper234
ripper234

Reputation: 230206

Can someone explain one of the algorithms that solves this Google Code Jam problem?

I'm referring to Shopping Plan problem from the Practice Problems. Here is a link to the solutions page.

Upvotes: 2

Views: 755

Answers (1)

Nikita Rybak
Nikita Rybak

Reputation: 68016

Without looking at the solutions, this appears to be a standard DP.

Each state is represented by the list of items left to buy (2^15 combinations) and current position of the car (50 stores + 1 original position = 51 possible options).

Transition from one state to others is easy.

def minCost(itemsLeft, currentPosition)
    current_minimum = INFINITY

    for (each store in the list) {
        if (store.containsSomeOf(itemsLeft)) {
            candidate = minCost(itemsLeft - store.items, store)  
                     + cost_of_items_bought_at_store + cost_of_driving
            current_minimum = min(current_minimum, candidate)
        }
    }

    return current_minimum
end

Naturally, itemList is represented as a bitmask and not an actual list.

You'll need to consider perishable items also, but that's purely technical.

Finally, you'll need to either apply memoization to recursion or rewrite it as pure DP.

Upvotes: 2

Related Questions