ナップザック問題で最適なグルメを求める（北海道編） 食べログのpythonスクレイピングと分析 #17

import pandas as pd

# カラム内のリストの要素を1つのリストに結合
result = [item for sublist in restaurant_data['ganre_tags'] for item in sublist]
unique_list = list(set(result))

ganre_info = {}

# ジャンル毎の平均をランチとディナーで求める
for genre_item in unique_list:
    selected_rows = restaurant_data[restaurant_data['ganre_tags'].apply(lambda x: genre_item in x)]
    lunch_value_mean = selected_rows['lunch_value_label'].astype(float).dropna().mean()
    dinner_value_mean = selected_rows['dinner_value_label'].astype(float).dropna().mean()
    selected_rows = selected_rows[selected_rows['score'] != '-']
    score_mean = selected_rows['score'].astype(float).dropna().mean()
    ganre_info[genre_item] = {
        'genre' : genre_item,
        'lunch_value_mean': lunch_value_mean,
        'dinner_value_mean': dinner_value_mean,
        'score_mean': score_mean,
    }

selected_keys = ['lunch_value_mean', 'score_mean', 'genre']
## キーの各valueを取得する。
## lunch_value_mean、score_mean、genreの各値が入ったリストのリストを作る（入れ子のリストになる）
value_list = [[d[key] for key in selected_keys] for d in ganre_info.values()]

N = len(ganre_info)  # 荷物の数
W = 14  # ナップサックの許容量 (価格帯は14)
filtered_data = [inner_list for inner_list in value_list if not any(np.isnan(x) for x in inner_list[:-1])]
filtered_data = [sublist for sublist in filtered_data if sublist[0] < 14]
wv = filtered_data
N = len(filtered_data)

# dpテーブルをベクトルで管理する
dp = [0] * (W + 1)
choice = [""] * (W + 1)

## ナップザック問題を解く
## 逆回しをしてdpテーブル更新の重複を避ける
for w, v, g in wv:
    for prev in range(W - int(w), -1, -1):
        new_v = dp[prev] + v
        if new_v > dp[prev + int(w)]:
            dp[prev + int(w)] = new_v
            choice[prev + int(w)] = choice[prev] + "1"
        else:
            choice[prev + int(w)] = choice[prev + int(w)] + "0"
    # 遷移できない場合はそのメニューを選べないため、0を付加する
    for i in range(int(w)):
        choice[i] += "0"
            
print(dp[-1], choice[-1])

## ジャンルを求める
best_genre = [wv[i][2] for i, bit in enumerate(choice[-1]) if bit == '1']
print(best_genre)