# 品物0～5の情報
# item[i][0]は品物iの重量
# item[i][1]は品物iの金額
item = [[0, 0], [3, 400], [4, 900], [2, 200], [5, 1200], [1, 150]]

# DPテーブル（初期状態）
# dp[i][j][0]はi行j列のマスの金額
# dp[i][j][1]はi行j列のマスに最後に入れた品物
dp = [
  [[0,""],[0,""], [0,""], [0,""], [0,""], [0,""], [0,""], [0,""]],
  [[0,""],["",""],["",""],["",""],["",""],["",""],["",""],["",""]],
  [[0,""],["",""],["",""],["",""],["",""],["",""],["",""],["",""]],
  [[0,""],["",""],["",""],["",""],["",""],["",""],["",""],["",""]],
  [[0,""],["",""],["",""],["",""],["",""],["",""],["",""],["",""]],
  [[0,""],["",""],["",""],["",""],["",""],["",""],["",""],["",""]]
]
      
# DPテーブルのi行j列のマスに部分問題の解を記入していく
for i in range(1, 6):
  for j in range(1, 8):
    # 品物iの重量がナップサックの耐重量jより大きい場合
    if item[i][0] > j:
      # 1つ上のマスの内容をコピーして記入する
      dp[i][j] = dp[i - 1][j]
    # そうでない場合
    else:
      # 品物iを選ばない場合の金額
      price1 = dp[i - 1][j][0]
      # 品物iを選んだ場合の金額
      price2 = dp[i][j - item[i][0]][0] + item[i][1]
      # 品物iを選ばない方が金額が大きい場合
      if price1 > price2:
        # 1つ上のマスの内容をコピーして記入する
        dp[i][j] = dp[i - 1][j]
      # そうでない場合
      else:
        # 品物iを選んだ金額を記入する
        dp[i][j][0] = price2
        # 品物iを最後に入れた品物として記入する
        dp[i][j][1] = i

# DPテーブルを表示する
print("【DPテーブル】")
for i in range(6):
  for j in range(8):
    if dp[i][j][1] == "":
      s = " なし"
    else:
      s = "品物" + str(dp[i][j][1])
    print(f"[{dp[i][j][0]:>4}円 {s}]", end="")
  print("")

# 問題全体の解（合計金額）を表示する
print("【合計金額】")
print(f"{dp[5][7][0]}円")

# 問題全体の解（選んだ品物）を表示する
print("【選んだ品物】")
j = 7
while dp[5][j][1] != "":
  # 最後に入れた品物を表示する
  print(f"品物{dp[5][j][1]} ", end="")
  print(f"({item[dp[5][j][1]][0]}kg, ", end="")
  print(f"{item[dp[5][j][1]][1]}円)")
  # その品物を取り出す
  j -= item[dp[5][j][1]][0]
