Pythonアルゴリズム（貪欲法）

貪欲法（Greedy Algorithm）は、ナップサック問題のように、与えられたリソースを効率的に利用する最適化問題に対する近似的な解を得るための手法

解く方法
➀価値/重量の比率を計算
➁アイテムを選ぶ：
ナップサックの容量 (b) が許す限り、価値/重量の比率が高いアイテムから順に選ぶ
➂許容量を超える場合、そのアイテムを部分的に追加（割合を計算して追加）
➃最終的に、選ばれたアイテムの割合を示す解ベクトル (x) と合計価値 (lb) を返す

import numpy as np

# ナップサック問題
c = np.array([50, 40, 10, 70, 55], dtype=np.float64)
# 価格
w = np.array([7, 5, 1, 9, 6], dtype=np.float64)
# 重さ
b = 15  # 最大許容量

def greedyKP(c, w, b):
    # 価値/重量の比率を計算し、この比率でアイテムを降順にソート
    ratio = c / w
    sorted_indices = np.argsort(-ratio)
    c, w = c[sorted_indices], w[sorted_indices]
    
    x = np.zeros(c.shape, dtype=np.float64)  # 解ベクトル
    w_sum = 0  # 現在の総重量
    lb = 0  # 下界（近似解の目的関数値）

    for i in range(c.shape[0]):
        # 現在のアイテムを追加すると容量を超える場合は、部分的に追加
        if w_sum + w[i] > b:
            x[i] = (b - w_sum) / w[i]
            lb += c[i] * x[i]
            break
        # それ以外の場合はアイテム全体を追加
        w_sum += w[i]
        x[i] = 1
        lb += c[i]
    
    return x, lb

# 与えられたデータで greedyKP 関数を実行
solution, lower_bound = greedyKP(c, w, b)
print(f"選ばれたアイテム（部分的な選択を含む）: {solution}")
print(f"選ばれたアイテムの総価値: {lower_bound}")

解説
c: 各アイテムの価値を格納した
ここでは 5 つのアイテムがあり、価値はそれぞれ
[50, 40, 10, 70, 55]
w: 各アイテムの重量を格納した配列
それぞれの重量は [7, 5, 1, 9, 6]
b: ナップサックの最大容量、つまり入れられるアイテムの重量の合計の上限。ここでは 15

    ratio = c / w
    sorted_indices = np.argsort(-ratio)
    c, w = c[sorted_indices], w[sorted_indices]

-ratioを使って降順に

    for i in range(c.shape[0]):

        if w_sum + w[i] > b:
            x[i] = (b - w_sum) / w[i]
            lb += c[i] * x[i]
            break
     
        w_sum += w[i]
        x[i] = 1
        lb += c[i]

容量を超えない場合:
w_sum += w[i]: アイテムの重量を合計に追加
x[i] = 1: アイテム全量を選ぶ
lb += c[i]: アイテムの価値を合計価値に追加
容量を超える場合:
x[i] = (b - w_sum) / w[i]: ナップサックの残りの容量に収まる分だけアイテムを部分的に選ぶ
lb += c[i] * x[i]: 部分的に選んだアイテムの価値を合計価値に追加
break: これ以上アイテムを追加できないため、ループを終了