C++で大きいものと小さいものの両方を交換できる場合に大きい方を最大化する方法

ここでは、大きなオブジェクト（例として「大きいおもちゃ」）と小さなオブジェクト（「小さいおもちゃ」）が与えられる問題を扱います。オブジェクトの種類は利用者が自由に決められますが、本稿ではサイズの特徴によって大きいもの・小さいものに分けられるおもちゃを例に取り上げます。求めるのは、小さいおもちゃを引き換えに渡すことで手に入る、大きいおもちゃの最大数です。

入出力の例

入力：big_toys = 8, small_toys = 20, a = 6, b = 4
出力：大きいものと小さいものの両方を交換できる場合の大きいおもちゃの最大数：11

解説：20個ある小さいおもちゃを使って引き換えられる大きいおもちゃの最大数は11個となります。

入力：big_toys = 3, small_toys = 10, a = 4, b = 2
出力：大きいものと小さいものの両方を交換できる場合の大きいおもちゃの最大数：5

解説：10個ある小さいおもちゃを使って引き換えられる大きいおもちゃの最大数は5個となります。

プログラムで使用するアプローチ

• 大きいおもちゃと小さいおもちゃの総数を入力します。また、a を「大きいおもちゃ1個を得るために必要な小さいおもちゃの数」、b を「大きいおもちゃ1個を手放したときに得られる小さいおもちゃの数」として扱います。

• a < b である場合、まず手元にあるすべての大きいおもちゃを小さいおもちゃに両替します。具体的には、小さいおもちゃの数を「現在の小さいおもちゃの総数 + b × 大きいおもちゃの総数」に更新し、大きいおもちゃの数を 0 にセットします。

• 次に、大きいおもちゃの数を「現在の大きいおもちゃの総数 + 小さいおもちゃの総数 ÷ a」に更新します。

• 小さいおもちゃとの引き換えで得られる大きいおもちゃの最大数が必要なため、大きいおもちゃの総数を返します。

• 結果を出力します。

このアルゴリズムの鍵となるのは、交換レートの比較です。大きいおもちゃ1個を手放すことで得られる小さいおもちゃの数 b が、大きいおもちゃ1個を新たに入手するために必要な小さいおもちゃの数 a よりも多い場合、一度すべてを小さいおもちゃに替えてから再度交換したほうが得になります。なお、小さいおもちゃの数を a で割る際は整数除算が行われるため、端数は切り捨てられます。

コード例

#include <iostream>
using namespace std;
int maximum(int big_toys, int small_toys,int a, int b){
    if (a < b){
        small_toys += b * big_toys;
        big_toys = 0;
    }
    big_toys += (small_toys / a);
    return big_toys;
}
int main(){
    int big_toys = 8, small_toys = 20;
    int a = 6, b = 4;
    cout<<"Maximize big when both big and small can be exchanged are:"<<maximum(big_toys, small_toys, a, b);
    return 0;
}

出力

Maximize big when both big and small can be exchanged are: 11