Pythonで予算内に購入できる車の最大台数を求める方法

問題の概要

販売中の車の価格リストと予算 k が与えられたとき、その予算内で購入できる車の最大台数を求める問題を考えます。

例えば、価格リストが [80, 20, 10, 30, 80]、予算が 85 の場合、出力は 3 になります。これは、価格 10・20・30 の3台を購入すると合計 60 となり、予算内に収まるためです。

解き方(アルゴリズム)

この問題は貪欲法(グリーディ法)を使うことで効率的に解けます。「同じ予算でできるだけ多くの車を買うなら、安い車から順に購入すればよい」というシンプルな発想です。

具体的な手順は以下の通りです。

• カウンター count を 0 で初期化します

• 価格リスト prices を昇順にソートします

• i を 0 から prices のサイズまでループさせます

  • prices[i] が k 以下の場合:

    • k から prices[i] を差し引きます

    • count を 1 増やします

  • それ以外の場合:

    • ループを抜けます

• 最後に count を返します

リストをソートしておけば、ある時点で予算を超える価格が出現した瞬間に、それ以降のすべての車も予算を超えることが保証されるため、途中でループを打ち切っても正しい答えが得られます。

実装例

以下はPythonでの実装例です。

class Solution:
    def solve(self, prices, k):
        count = 0
        prices.sort()
        for i in range(len(prices)):
            if(prices[i] <= k):
                k = k - prices[i]
                count += 1
            else:
                break
        return count

ob = Solution()
p = [80, 20, 10, 30, 80]
print(ob.solve(p, 85))

入力

[80, 20, 10, 30, 80], 85

出力

3

計算量の目安

ソートに O(n log n)、その後の走査に O(n) かかるため、全体の時間計算量は O(n log n) です。また、追加のデータ構造を使用しないため、空間計算量は O(1)(インプレースソートの場合)となります。リストの要素数が多くても効率よく処理できるのが特徴です。