二分探索④：平均最大化（全４回）

平均最大化

二分探索 を使って、平均最大化問題 を解いてみます。

問題

重さと価値がわかっている品物が複数あります。

この中から、ｋ個選んだ時の重さあたりの価値の最大値を求めてください。

ソースコード

この問題は 重さあたりの価値がｘ以上となるように選ぶことができるかどうか という関数を定義し、二分探索で最大のｘを求める ことで解くことができます。

関数としては、それぞれの品物に対して（価値 - 重さあたりの価値[x] × 重さ）を計算し、この結果の大きいほうからｋ個の和を求めて、それが０以上かどうかで判定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#------ 入力例 ------
k = 2           # 選択する個数
# それぞれの品物の重さと価値
items = [{'weight':2, 'value':2},
         {'weight':5, 'value':3},
         {'weight':2, 'value':1}]
#--------------------
# 重さあたりの価値[x]が実現可能かどうか
def check(x):
    # それぞれの品物に対して、（価値 - 重さあたりの価値[x] × 重さ）を計算する
    res = [item['value'] - x * item['weight'] for item in items]
    res = sorted(res, reverse=True) # 大きいほうからソート
    return sum(res[:k]) >= 0  # 大きいほうからｋ個の和が０以上かどうか

# 解の存在範囲を初期化
lb, ub = 0, 999
for _ in range(100):      # 十分な回数繰り返す
    mid = (lb + ub) / 2   # 解の存在範囲の中央値
    if check(mid):        # 中央値が実現可能かどうか
        lb = mid
    else:
        ub = mid
print('解：', lb)

[実行結果]

解： 0.75

解は 0.75 となりました。

品物の価値と重さを確認すると、１つめと３つめの品物を選んで重さあたりの価値を計算すると (2 + 1) / (2 + 2) = 0.75 となり 最大値 となっていることが確認できます。