def solve_knapsack():
    # --- 設定値 ---
    # 表1および追加の品物Cの情報 [cite: 8, 25]
    # 品物A: 容積1, 価値2 / 品物B: 容積2, 価値6 / 品物C: 容積3, 価値9
    size = [1, 2, 3]
    value = [2, 6, 9]
    N = len(size)  # 品物の種類数 
    V = 5          # 容量制限 

    # --- 初期化 [cite: 32-38] ---
    maxvalue = [0] * (V + 1)
    choice = [-1] * (V + 1)  # -1は品物が選ばれていないことを示す [cite: 37]

    # --- 動的計画法メイン [cite: 39-49] ---
    for s in range(N):  # sを0からN-1まで [cite: 40]
        # tをsize[s]からVまで増やすことで、重複選択を可能にする 
        for t in range(size[s], V + 1):
            # [オ] の処理: 新しく品物sを追加した場合の価値 [cite: 42]
            temp = maxvalue[t - size[s]] + value[s]
            
            # [カ] の処理: 既存の最大価値より大きければ更新 [cite: 43-45]
            if temp > maxvalue[t]:
                maxvalue[t] = temp
                choice[t] = s  # 最後に選んだ品物を記録 [cite: 46]

    # --- 結果の出力（逆しらべ） [cite: 50-60] ---
    print("選んだ品物のインデックス:")
    k = V  # [cite: 51]
    items_count = [0] * N
    
    while choice[k] >= 0:  # [cite: 52]
        item_index = choice[k]
        print(f"品物 {item_index}") # [cite: 53]
        items_count[item_index] += 1
        
        # [キ] の処理: 選んだ品物の容積分だけ容量を戻す [cite: 54, 57-59]
        k = k - size[item_index]
    
    # [ク] の処理: 最終的な最大価値を出力 [cite: 56, 60]
    print(f"\n最大価値合計: {maxvalue[V]}")
    
    # 各品物の個数（設問1(2)の確認用）
    for i, count in enumerate(items_count):
        name = chr(65 + i) # 0->A, 1->B, 2->C
        print(f"品物{name}: {count}個")

if __name__ == "__main__":
    solve_knapsack()