C++でax + by + cz = nを満たすx + y + zの最大値を求める方法

整数 a、b、c、n が与えられたとき、ax + by + cz = n を満たす x + y + z の合計を最大化することが目標です。

式の導出

与えられた式から、z は次のように表すことができます。

cz = n − (ax + by)
z = (n − (ax + by)) / c

x と y を固定すれば、この式から z を一意に求められます。すべての x・y の組み合わせについて z を計算し、その合計 x + y + z を求めます。そして、条件を満たす組み合わせの中で最も大きい合計を答えとして記録していきます。

入力例と出力例

例1

n = 6, a = 3, b = 4, c = 5;

出力:

maximum x+y+z is 2.

説明: x = 2、y = 0、z = 0 のとき ax + by + cz = n が成り立ちます。

3×2 + 0×4 + 0×5 = 6 = n

例2

n = 4, a = 3, b = 1, c = 2;

出力:

maximum x+y+z = 4

説明: x = 0、y = 4、z = 0 のとき ax + by + cz = n が成り立ちます。

0×3 + 4×1 + 0×2 = 4 = n

プログラムのアプローチ

• 整数 a、b、c、n を式 ax + by + cz = n に使用します。
• 関数 maximize(int n, int a, int b, int c) は a、b、c、n を引数として受け取り、ax + by + cz = n を満たす x + y + z の最大値を返します。
• 可能なすべての ax の値をループで走査します(for(i = 0; i <= n; i += a))。
• 同様に、可能なすべての by の値も走査します(for(j = 0; j <= n; j += b))。
• z = (n − (ax + by)) / c を計算します。
• x = i / a、y = j / b として x + y + z を計算し、変数 temp に格納します。
• temp がそれまでの maxx 以上であれば、maxx を更新します。
• 最後に maxx を目的の合計として返します。

なお、z は整数でなければならないため、floor(z) == ceil(z) によって z が整数になる場合のみ解として採用しています。条件を満たす組み合わせが存在しない場合は 0 が返されます。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int maximize(int n, int a, int b, int c){
    int maxx = 0;
    // i は ax の取りうる値
    for (int i = 0; i <= n; i += a)
        // j は by の取りうる値
    for (int j = 0; j <= n - i; j += b) {
        float z = (n - (i + j)) / c;
        // z が整数の場合のみ有効な解
        if (floor(z) == ceil(z)) {
            int x = i / a;
            int y = j / b;
            int temp = x + y + z;
            if (temp >= maxx)
                maxx = temp;
        }
    }
    return maxx;
}
int main(){
    int n = 6, a = 3, b = 4, c = 5;
    cout << "Maximized the value of x + y + z :" << maximize(n, a, b, c);
    return 0;
}

出力

Maximized the value of x + y + z :2

計算量について

この手法は二重ループによる全探索(ブルートフォース)であり、時間計算量はおよそ O(n² / (a × b)) になります。そのため n が小さい範囲では十分実用的ですが、n が非常に大きくなる場合は動的計画法(DP)などの別のアプローチを検討するとよいでしょう。