「python Adventvent Calendar 2017 16日目」TDLアトラクションの組み合わせ最適化をしてみる

import numpy as np

attractions = ["オムニバス", "ジャングルクルーズ", "カリブの海賊", "ウエスタンリバー鉄道", "魅惑のチキルーム"
             , "スイスファミリーのツリーハウス", "ビッグサンダーマウンテン", "カントリーベア", "蒸気船マークトレイン号"
             , "トムソーヤ島いかだ", "スプラッシュマウンテン", "ビーバーブラザーズのカヌー探検", "プーさんのハニーハント"
             , "ホーンテッドマンション", "ピーターパンの空の旅", "空飛ぶダンボ", "白雪姫と七人の小人", "ピノキオの冒険旅行"
             , "イッツ・ア・スモールワールド", "アリスのティーパーティー", "キャッスルカルーセル", "ミッキーのフィルハーマジック"
             , "シンデレラのフェアリーテイル・ホール", "ロジャーラビットのカートゥーンスピン", "ガジェットのゴーコースター"
             , "モンスターズインク~ライド＆ゴーシーグ~", "バズ・ライトイヤーのアストロブラスター", "スペースマウンテン", "スター・ツアーズ"]
# 優先度
points = np.array([2,8,10,4,2,3,9,1,3,7,6,2,8,5,10,1,3,3,5,1,1,7,2,2,7,10,8,6,7])
# [平均待ち時間,体験時間]
time = np.array([[4,6],[28,10],[18,15],[18,15],[11,10],[0,9],[74,4],[16,17],[15,12]
                ,[6,3],[95,10],[20,10],[88,5],[67,15],[48,3],[41,2],[26,3],[22,2],[18,10]
                ,[13,2],[12,2],[60,15],[20,8],[38,4],[23,1],[99,4],[69,4],[69,3],[13,5]])
# 制限時間
limit_time = 300

def greedy():

    # 各アトラクションにかかる合計時間
    per_time = 0
    # もっとも優先度が高いアトラクションのインデックス
    best_idx = 0
    # 合計ポイント
    total_point = 0

    global limit_time

    while (limit_time >= 0):
        best_idx = np.argmax(points)

        per_time = sum(time[best_idx])
        limit_time -= per_time
        if (limit_time <= 0): break

        total_point += points[best_idx]
        points[best_idx] = 0

        print(attractions[best_idx])

    print(total_point)

カリブの海賊
ピーターパンの空の旅
モンスターズインク~ライド＆ゴーシーグ~
ビッグサンダーマウンテン
39

def dinamic_programming():
    # グリッド
    grid = np.zeros([points.size, limit_time])
    # 各アトラクションの合計所要時間（待ち時間＋体験時間）
    per_time = 0
    # 各アトラクションの合計所要時間のリスト
    per_time_list = []

    per_time = sum(time[0])
    per_time_list.append(per_time)



    for j in range(limit_time):
        grid[0][j] = 0 if j+1 < per_time else points[0]

    for i in range(1, points.size):
        per_time = sum(time[i])
        per_time_list.append(per_time)
        for j in range(limit_time):
            if j+1 < per_time:
                grid[i][j] = grid[i-1][j]
            elif j+1 == per_time:
                grid[i][j] = max(grid[i-1][j], points[i])
            elif j+1 > per_time:
                grid[i][j] = max(grid[i-1][j], grid[i-1][j-per_time]+points[i])


    print(np.max(grid[np.size(points)-1]))
    for attraction in answer_best_attraction(grid, per_time_list):
        print(attraction)


def answer_best_attraction(grid, per_time_list):
    best_attraction_list = []

    i = len(attractions)-1
    j = np.argmax(grid[i])
    while (i >= 0):
        if grid[i][j] != grid[i-1][j]:
            best_attraction_list.append(attractions[i])
            j -= per_time_list[i]
        i -= 1

    return best_attraction_list

68.0
スター・ツアーズ
ガジェットのゴーコースター
イッツ・ア・スモールワールド
ピーターパンの空の旅
トムソーヤ島いかだ
ビッグサンダーマウンテン
スイスファミリーのツリーハウス
カリブの海賊
ジャングルクルーズ
オムニバス