問題解決法（ナップサック問題）

方法論：

貪欲法（値段の比率が高いものから埋める）

総当たり法（全部の組み合わせを調べる）

動的計画法（帰納的に、計算履歴を利用して解く）

# 品物のリストを作る(namedtuple)

from collections import namedtuple
import random

random.seed(7)

Item = namedtuple('Item', ('name', 'weight', 'price'))

num = 20

item_list = []
max_weight = 5
max_price = 50

price_list = list(range(1, max_price+1))
random.shuffle(price_list)

for i in range(num):
  w = random.randint(1, max_weight)
  item = Item(i, w, price_list.pop())
  item_list.append(item)


item_list

class Knapsack:

  def __init__(self, size):
    self.size = size
    self.weight = 0
    self.value = 0
    self.items = []
  
  def append(self, item):
    if not self.has_room_for(item):
      raise ValueError('重量オーバー')
    self.items.append(item)
    self.weight += item.weight
    self.value += item.price

  def has_room_for(self, item):
    return self.size >= self.weight + item.weight
  
  def __str__(self):
    val = '重さ {} kg / 価値 {} 万円'.format(self.weight, self.value)
    return val

# 貪欲法
knap1 = Knapsack(40)

def greedy(item_list, knap):
  item_list_sorted = sorted(
      item_list, 
      key=lambda x: x.price/x.weight, 
      reverse=True
      )
  for item in item_list_sorted:
    while knap.has_room_for(item):
      knap.append(item)
  return knap.__str__()