Pythonで果物かごを満たすための最小コストを効率的に求めるプログラム

問題の概要

fruitsというリストと、2つの値k・capが与えられているとします。リストの各要素fruits[i]は3つの値[c, s, t]からなり、それぞれ「果物iの1個あたりのコストc」「果物1個のサイズs」「果物iの在庫数t」を意味します。また、kは容量capの果物かごの本数を表します。

このとき、以下の制約をこの順序で守りながら、かごに果物を詰めていきます。

• 各かごに入れられるのは同じ種類の果物のみ
• 各かごはできる限り満杯に近づける
• 各かごのコストはできる限り安く抑える

これらの条件のもとで、できるだけ多くのかごを満たすために必要な最小コストを求めるのが目的です。

入力例と出力例

例として、fruits = [[5, 2, 3], [6, 3, 2], [2, 3, 2]]、k = 2、cap = 4 の場合を考えてみましょう。このときの出力は12になります。

理由は次のとおりです。まず果物0(コスト5、サイズ2、在庫3)を2個使うと、合計サイズは2+2=4となり、最初のかごをちょうど満杯にできます。このときのコストは5+5=10です。次のかごには、より安い果物2(コスト2、サイズ3、在庫2)を1個入れます。こちらのコストは2なので、合計コストは10+2=12となります。

解法のアプローチ

この問題は貪欲法(グリーディ法)を用いて解くことができます。大まかな流れは、「各果物の種類ごとに『1かご分の詰め合わせ』を候補として列挙し、それらを満杯度とコストの順で並べ替えて、安くて満杯に近いかごから順に採用していく」というものです。具体的な手順は以下のとおりです。

1. 候補を格納する空のリストoptionsを用意する
2. fruits内の各组(c, s, t)について、以下を繰り返す
     ・t > 0 の間、次の処理を続ける
     ・fnum := min(cap // s, t) … 1かごに入る最大個数を求める
     ・fnum == 0 ならループを抜ける(サイズが容量を超えて入りきらない場合)
     ・bnum := t // fnum … この詰め合わせで作れるかごの本数
     ・(余り容量 cap − fnum×s、かご1本分のコスト fnum×c、本数 bnum) をoptionsに追加
     ・t := t − bnum×fnum で残りの在庫を更新する
3. 答えansを0で初期化する
4. optionsをソートしたリストの各要素(left_cap, bcost, bnum)について、以下を処理する
     ・bfill := min(k, bnum)
     ・ans := ans + bcost × bfill
     ・k := k − bfill
     ・k == 0 になったらループを抜ける
5. ansを返す

ここでのポイントは、optionsをタプルのままソートすると、余り容量(left_cap)が小さい順、つまり「より満杯に近いかご」が先頭に来る点です。さらに余り容量が同じ場合はコストの安いものが先になります。これにより、「満杯優先・そのうえで低コスト優先」という制約を自然に満たす貪欲な戦略が実現します。

Pythonによる実装例

それでは、実際の実装を見てみましょう。

def solve(fruits, k, cap):
    options = []
    for c, s, t in fruits:
        while t > 0:
            fnum = min(cap // s, t)
            if fnum == 0:
                break
            bnum = t // fnum
            options.append((cap - fnum * s, fnum * c, bnum))
            t -= bnum * fnum
    ans = 0
    for left_cap, bcost, bnum in sorted(options):
        bfill = min(k, bnum)
        ans += bcost * bfill
        k -= bfill
        if k == 0:
            break
    return ans

fruits = [[5, 2, 3], [6, 3, 2], [2, 3, 2]]
k = 2
cap = 4
print(solve(fruits, k, cap))

入力

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

出力

12

まとめ

このアルゴリズムでは、まず各果物の種類ごとにかご1本分の詰め合わせ候補を生成し、その後ソートによって「満杯に近く、かつ安いかご」を優先的に選んでいます。候補数をMとすると、ソートのコストはO(M log M)程度に収まるため、在庫数やかご候補の数に対して効率的に動作します。貪欲法の典型的な応用例として、条件付きの割り当て問題をシンプルなコードで解ける良い例といえるでしょう。