欲張り法

はじめに

講義でナップサック問題の効率化をする問題があって、いい感じに出来たのでメモ

コード

import numpy as np

B = 55 # 袋の容量
size = [3,6,5,4,8,5,3,4,3,5,6,4,8,7,11,8,14,6,12,4] # 荷物の容量
price = [7,12,9,7,13,8,4,5,3,10,7,5,6,14,5,9,6,12,5,9] # 価格
N = len(size) # 荷物の個数

bag = []
sum_size = 0
sum_price = 0
result = []

# 価格/サイズが大きい順にソート
for i, j, k in zip(size, price, range(N)):
    bag.append((j/i, i, j, k))
    new_bag = sorted(bag, reverse = True)

# 価格/サイズが大きい荷物からバッグに入れていく
for i in range(N):
    if sum_size+new_bag[i][1] <= B:
        result.append(new_bag[i][3]+1)
        sum_size += new_bag[i][1]
        sum_price += new_bag[i][2]

print("合計が最大になる組み合わせ", sorted(result))
print("合計価格：", sum_price)
print("合計サイズ：", sum_size)