Pythonでトラックに積載できる最大ユニット数を求めるプログラム（貪欲法による解法）

問題の概要

2次元配列 boxTypes が与えられます。各要素 boxTypes[i] は [i番目の種類の箱の個数, 1箱あたりのユニット数] の形式で表されます。さらに、トラックに積める箱の最大数を示す値 k も与えられます。

箱の総数が k を超えない範囲であれば、どの箱を選んでトラックに積んでも構いません。この条件のもとで、トラックに積載できるユニットの合計の最大値を求めましょう。

入力例

boxTypes = [[2,4],[3,3],[4,2]]、k = 6 の場合、出力は 19 になります。箱の内訳は以下の通りです。

• 種類1の箱：2個（それぞれ4ユニット入り）
• 種類2の箱：3個（それぞれ3ユニット入り）
• 種類3の箱：4個（それぞれ2ユニット入り）

k = 6 なので、種類1と種類2の箱をすべて積み、残りの枠1つ分には種類3の箱を1個だけ積めます。したがって、(2×4) + (3×3) + (1×2) = 8 + 9 + 2 = 19 ユニットが答えとなります。

解き方：貪欲法（グリーディ法）

この問題は「貪欲法」と呼ばれるアプローチで効率的に解けます。基本の考え方はシンプルで、1箱あたりのユニット数が多い箱から順に積んでいくというものです。手順は以下の通りです。

1. boxTypes を、1箱あたりのユニット数の降順でソートする
2. 変数 total := 0、fill := 0 を初期化する
3. boxTypes の各要素 i に対して以下を繰り返す
   • fill + i[0] <= k の場合：その種類の箱をすべて積み、fill += i[0]、total += i[0] * i[1] と更新する
   • それ以外の場合：残りの空きスペース分だけ積み、total += (k - fill) * i[1] を加算してループを抜ける
4. total を返す

Pythonでの実装例

実際のコードは以下のようになります。

def solve(boxTypes, k):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    total = 0
    fill = 0
    for i in boxTypes:
        if fill + i[0] <= k:
            fill += i[0]
            total += i[0] * i[1]
        else:
            total += (k - fill) * i[1]
            break
    return total

boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))

入力

[[2,4],[3,3],[4,2]], 6

出力

19

計算量の目安

ソートに O(n log n)、その後の走査に O(n) を要するため、全体の時間計算量は O(n log n) です。ソートをインプレースで行えば、追加のメモリはほぼ不要で、空間計算量は O(1) に抑えられます。このように、単位あたりの価値が高いものから詰めていく貪欲戦略は、この種のナップサック型問題において最適解を保証できる代表的な手法です。