C++で所持金K以内に収まるおもちゃの最大購入数を求めるアルゴリズム

この記事では、おもちゃの価格リスト（配列）と手元にある金額Kが与えられたとき、その予算内で購入できるおもちゃの数を最大化する問題をC++で解く方法を解説します。配列の各要素は1つのおもちゃの価格を表しており、配列の要素数がおもちゃの総数に相当します。

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。まず価格の配列を昇順にソートし、できるだけ多くのおもちゃを買えるよう、安いおもちゃから順番に購入していくという戦略です。高価なおもちゃは後回しにすることで、限られた予算で最大数を確保できます。

入力例

toyprices[] = { 10, 20, 12, 15, 50, 30 }　K = 50

出力例

Maximum no. of toys that can be purchased : 3

解説： おもちゃの価格を昇順にソートすると { 10, 12, 15, 20, 30, 50 } となります。

1個目のおもちゃを購入： K=50, count=1, 残金 = 40（50-10）
2個目のおもちゃを購入： K=40, count=2, 残金 = 28（40-12）
3個目のおもちゃを購入： K=28, count=3, 残金 = 13（28-15）
次のおもちゃの価格は20なので残金13では買えず、count=3で終了

別の入力例

toyprices[] = { 50, 40, 30, 20, 10 }　K = 25

出力例

Maximum no. of toys that can be purchased : 1

解説： 25円あれば10円と20円のおもちゃはそれぞれ単体なら買えますが、両方買うには10+20=30円が必要なため同時には買えません。したがって最大購入数は1です。

プログラムのアプローチ

• 整数型配列 toyprice[] におもちゃの価格を格納します。

• 関数 maxToys(int price[], int N, int K) が、価格配列・その要素数N・所持金Kを受け取ります。

• 変数 toycount は購入できるおもちゃの数を保持し、初期値は0です。

• 変数 spent は、これまでにKからいくら支出したかを記録します。

• sort(price, price + N); を使って価格配列を昇順にソートします。

• 最安値の price[0] から最高値まで順に配列を走査します。

• おもちゃの価格を spent に加算してもK以下になる場合は、そのおもちゃを購入できたものとして toycount を1増やし、spent = spent + price[i] で支出額を更新します。

• 配列がソート済みのため、予算を超えた時点でループを抜けて構いません。

• 最終的に toycount に購入可能なおもちゃの数が入ります。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int maxToys(int price[], int N, int K){
    int toycount = 0;
    int spent = 0; // 支出はKまでに抑える
    // 安い価格から先に来るようにソート
    sort(price, price + N);
    for (int i = 0; i < N; i++) {
        if (spent + price[i] <= K){
            spent = spent + price[i];
            toycount++;
        } else
            break; // ソート済みなので以降はすべて予算オーバー
    }
    return toycount;
}
int main(){
    int budget = 100;
    int toyprice[] = { 10, 120, 50, 11, 20, 100, 10, 90, 12, 15 };
    int N = 10;
    cout <<"Maximum no. of toys that can be purchased : "<< maxToys(toyprice, N, budget) ;
    return 0;
}

出力

Maximum no. of toys that can be purchased : 6

このように、価格を昇順ソートして安い順に購入していくシンプルな貪欲法により、O(N log N)の計算量で最大購入数を求めることができます。競技プログラミングでも頻出のパターンなので、ぜひ覚えておきましょう。