誰かがこのGoogle Code Jamの問題を解決するアルゴリズムの1つを説明できますか？

Question

私は練習問題からShopping Plan problemを参照しています。ここにthe solutions pageへのリンクがあります。

Answer 1

解決策を見ることなく、これは標準DPのように見えます。各状態は、アイテムのリストで表される

は、（= 51可能なオプションを50格納+ 1原位置）（2^15組み合わせ）を購入し、車の現在位置に残しました。

ある状態から他の状態への遷移は簡単です。

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 

当然、itemListはビットマスクではなく、実際のリストとして表されます。

傷みやすいアイテムも考慮する必要がありますが、それはまったく技術的なものです。

最後に、再帰にmemoizationを適用するか、純粋なDPとして書き直す必要があります。