動的計画法のお勉強

import pandas as pd
from dataclasses import dataclass
from typing import Tuple, List
from functools import lru_cache


@dataclass
class Item:
    name: str
    weight: int  # 価格
    value: int  # カロリー


def load_items_from_csv(file_path: str) -> List[Item]:
    menu_df = pd.read_csv(file_path)
    return [
        Item(row["name"], row["price"], row["calorie"]) for _, row in menu_df.iterrows()
    ]


items = load_items_from_csv("menu.csv")


@lru_cache(None)
def knapsack_recursive_with_items(i: int, size: int) -> Tuple[int, List[Item]]:
    """ナップザック問題を解く再帰関数（結果とアイテムの組み合わせを返す）"""
    if i < 0 or size <= 0:
        return 0, []

    # i番目のアイテムがナップザックに入らない場合
    value_without_i, items_without_i = knapsack_recursive_with_items(i - 1, size)

    if size < items[i].weight:
        return value_without_i, items_without_i
    else:
        # i番目のアイテムをナップザックに入れる場合
        value_with_i, items_with_i = knapsack_recursive_with_items(
            # i - 1             # 重複なし
            i,  # 重複あり
            size - items[i].weight,
        )
        value_with_i += items[i].value

        if value_with_i > value_without_i:
            return value_with_i, items_with_i + [items[i]]
        else:
            return value_without_i, items_without_i


def main():
    # 1000円以下でカロリーを最大化するメニューの組み合わせを計算
    max_calories_combination = knapsack_recursive_with_items(len(items) - 1, 1000)

    # 結果の表示
    total_price = sum(item.weight for item in max_calories_combination[1])
    print(f"Total Price: {total_price} yen")
    print(f"Total Calories: {max_calories_combination[0]} kcal")
    print("Selected Items:")
    for item in max_calories_combination[1]:
        print(f"- {item.name}: {item.weight} yen, {item.value} kcal")


if __name__ == "__main__":
    main()