Pythonアルゴリズム（線形緩和法）

線形緩和法（もしくは緩和問題）は、貪欲法と似ているが、目的は「上界」を計算すること

def optimizeRelaxedKP(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  # 現在の総重量
    ub = 0  # 上界（緩和問題における目的関数値）

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

貪欲法と線形緩和法の違い
目的の違い:
貪欲法は近似的な解を求めるために使用される。このため、実行される結果はすぐに使える（実行可能）解であり、選ばれたアイテムの総価値の下界を示す。

線形緩和法は、理論的に取り得る最大の価値を求めるために使用されれる。このため、実行される結果は上界を示し、部分的に選んだアイテムも含める。得られた解は実行可能ではない場合もある（緩和された理論上の最大値であり、実際に全てのアイテムを入れられない可能性がある）。

変数名の違い:
貪欲法の結果として得られるのは「下界」 (lb) であり、近似的な解の価値
緩和問題の結果として得られるのは「上界」 (ub) であり、理論上取り得る最大の価値

使用される場面
貪欲法:
近似解を迅速に得たい場合や、最適解でなくても良い状況（特に制限された計算リソースで）。計算量が膨大な場合など

線形緩和法:
分枝限定法などで「上界」を計算する必要がある場合。これにより、探索を効率化し、不要な分枝を早期に刈ることができる。