Fractional Knapsack
n 個の品物があります。品物 i の価値は values[i] で、重さは weights[i] です。バッグに入れられる重さの合計は最大で capacity で、品物の一部だけを取ることもできます。品物 i の重さが w の部分の価値は values[i] × w / weights[i] です。
バッグに入れられる価値の合計の最大値を返し、小数点以下を切り捨てて整数にする fractionalKnapsack という名前の関数を書いてください。
関数
- valuesinteger-array
- 各アイテムの価値
- weightsinteger-array
- 各アイテムの重さ
- capacityinteger
- バッグが入れられる最大の重量
- 戻り値integer
- バッグに入る最大の合計価値を切り捨てた値
制約
1 ≤ n ≤ 5000。ここで、n = values.length = weights.length1 ≤ values[i], weights[i] ≤ 1041 ≤ capacity ≤ 108
例
- 入力
- values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
- 出力
- 151
- 説明
- 重量1単位あたりの品物の価値は5、3、6、2.5です。品物2と0を丸ごと入れると価値は70で、残りの容量は27です。品物1の30単位のうち27単位を加えると81になり、合計は151です。
- 入力
- values = [10, 7]weights = [4, 3]capacity = 5
- 出力
- 12
- 説明
- アイテム 0 は単位あたり 2.5 の価値があり、アイテム 1 は約 2.33 なので、アイテム 0 を丸ごと入れると 10 になります。アイテム 1 の 3 単位のうち 1 単位を加えると
7 / 3となり、12 と 3 分の 1 は切り捨てられて 12 になります。
- 入力
- values = [5, 8]weights = [2, 3]capacity = 100
- 出力
- 13
- 説明
- どちらの品物も余裕をもって収まるので、すべて持っていきます：5 + 8 = 13。
発展問題
すべての品目をソートせずに、O(n) 時間で答えを見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
バッグに重さをあと1単位分入れる余裕があるとしたら、どのアイテムからその1単位分を取りますか？
重さの単位あたりの価値が最も高いのは、重さあたりの価値が最も高い品物から取る場合です。最も密度の高い品物から順にバッグを満たし、切り分けるのは最後に扱う品物だけです。
密度の高い順にアイテムを並べ、割り算をしなくて済むように
values[a] × weights[b]とvalues[b] × weights[a]を比較します。入る間はアイテムを丸ごと取り、その後、バッグを満たすアイテムには整数除算でvalues[i] × room / weights[i]を加えます。
解説
品物を分割できるため、この問題は0/1ナップサック問題とは異なり貪欲法で解けます。残っている品物のうち、単位重量あたりの価値が最も高いものから、重量を1単位ずつ使います。その密度で並べ替え、順にバッグを満たします。密度は交差乗算で比較し、分割する品物だけを切り捨てれば、端数を保存する必要はありません。
各ラウンドで最も密度の高いアイテムを選ぶ
正しいが、最大のテストでは終わらない
考え方
密度が最も高い品物から順にバッグに詰めます。入るなら丸ごと取り、入らない場合はバッグを満たす分だけ取り、そこで止めます。すべての品物を走査して、割り算をせずに values[i] × weights[j] と values[j] × weights[i] を比較し、未使用の品物の中で最も密度が高いものを見つけます。重さが正なら同じ判定になり、どちらの積も 10^8 以下です。
密度が高い順に取るのが最善です。荷物に密度の低い品物がある程度含まれていて、密度の高い品物がまだ全部入っていないなら、その分を密度の高い品物に入れ替えても価値は下がりません。入れ替えを続ければ、密度が高い順に詰めた状態になります。
最大 n 回の各ラウンドで未使用の品物を走査するため、n = 5000 のとき、比較回数はおよそ n²/2 = 12.5 million です。
アルゴリズム
- すべての品目を未使用として印を付け、
room = capacityとtotal = 0を設定します。 - 容量に余裕がある間、未使用の品目を調べ、交差乗算で密度を比較して最も密度の高いものを探します。
- 品目が残っていなければ終了します。そうでなければ、その品目を使用済みとして印を付けます。
- 入る場合は、その価値を
totalに加え、その重さをroomから差し引きます。入らない場合は、整数除算でvalues[i] × room / weights[i]を加えて終了します。 totalを返します。
def fractionalKnapsack(values, weights, capacity):
n = len(values)
used = [False] * n
total = 0
room = capacity
while room > 0:
best = -1
for i in range(n):
# i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
best = i
if best == -1:
break # every item is already in the bag
used[best] = True
if weights[best] <= room:
total += values[best]
room -= weights[best]
else:
total += values[best] * room // weights[best] # the part that fits, rounded down
room = 0
return total重量あたりの価値で並べ替える
考え方
スキャンでは最も密度の高い品目を何度も探しますが、ラウンドごとに順序が変わることはありません。同じ交差乗算による比較を使って、品目を一度だけ密度の高い順に並べ替えます。密度が等しい品目は、単位あたりの価値が同じなので、どちらの順序でもかまいません。
入る間は品目を丸ごと取ります。入らない最初の品目だけを切り分けます。これによって values[i] × room / weights[i] が加算され、整数除算では端数が切り捨てられます。それより前の品目はすべて整数個なので、この項だけを丸めれば正確な答えになります。ソートの計算量は O(n log n)、走査の計算量は O(n) です。
アルゴリズム
- 品目のインデックスのリストを作成し、交差乗算による比較を使って密度の高い順に並べ替えます。
room = capacityおよびtotal = 0を設定します。- その順序で各品目について、
weights[i] ≤ roomなら、その価値を加算し、重さの分だけroomを減らします。 - そうでなければ、整数除算で
values[i] × room / weights[i]を加算して終了します。 totalを返します。
from functools import cmp_to_key
def fractionalKnapsack(values, weights, capacity):
# a goes before b when values[a] / weights[a] > values[b] / weights[b],
# tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
def denser_first(a, b):
return values[b] * weights[a] - values[a] * weights[b]
order = sorted(range(len(values)), key=cmp_to_key(denser_first))
total = 0
room = capacity
for i in order:
if weights[i] <= room:
total += values[i] # the whole item fits
room -= weights[i]
else:
total += values[i] * room // weights[i] # the part that fits, rounded down
break
return total
落とし穴と境界ケース
- 価値だけ、または重さだけで並べ替えること。最初の例では、価値が90の品物は価値密度で3番目です。それを最初に取ると、価値が50の品物を半分だけ入れる余地が残り、合計は151ではなく115になります。
- 掛け算の前に割り算をすること。価値が13、重さが7で、残り容量が3の場合、整数演算での
13 / 7 * 3は3になりますが、13 * 3 / 7なら正しい値の5になります。 - 毎回品物を分割すると思い込むこと。3つ目の例ではすべての品物が入るため、答えはすべての価値の合計である13です。
よくある質問3
分数ナップサック問題の時間計算量はどれくらいですか？
価値を重量で割った値で品目を並べ替えるには O(n log n) のコストがかかり、詰め込みは1回の走査で済むため、合計は O(n log n)、順序を保持するための空間計算量は O(n) です。各ラウンドで最も密度の高い品目を走査して探すと、コストは O(n²) です。
なぜ貪欲法は分割可能ナップサックではうまくいくのに、0/1ナップサックではうまくいかないのでしょうか？
分割すれば、密度の低い品物の重量を、より密度の高い品物に置き換えられます。分割できない場合、密度の高い品物を選ぶと、ほかの品物では埋められない空きが残ることがあります。価値が 8、11、15、重量が 2、3、4、容量が 7 の場合、密度の高い順に選ぶと重量 2 と 4 の品物を取り、価値は 23 になりますが、重量 3 と 4 の品物を選ぶと価値は 26 になります。0/1 版には動的計画法が必要です。
浮動小数点数を使わずに分数ナップサック問題を解くにはどうすればよいですか？
重みが正の場合、a / b > c / dはa × d > c × bと同じ判定なので、交差乗算して密度を比較します。最適な値は整数と1つの分数の和であり、切り分ける品目についてはvalues[i] × room / weights[i]となるため、整数除算を1回行うだけで、切り捨てた答えが正確に得られます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def fractionalKnapsack(values, weights, capacity):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
values = [40, 90, 30, 50] weights = [8, 30, 5, 20] capacity = 40
期待される出力
151