C++で車の売却による最大利益を求めるプログラムの作成方法

問題の概要

赤と青の2色の車に対する販売需要があるとします。ある自動車会社は、価格の異なる赤い車をp台、青い車をq台販売することに決めました。現在、同社の在庫には赤い車がa台、青い車がb台、そしてまだ塗装されていない無彩色の車がc台あります。各車の価値は配列A、B、Cとして与えられます。同社は1日あたりp + q台の車を販売し、そこから利益を最大化しなければなりません。無彩色の車は、赤または青のどちらの色にも塗装することが可能です。この記事では、車の販売によって得られる最大の利益を求める方法を解説します。

入力例と出力

たとえば、入力が p = 3、q = 3、a = 3、b = 3、c = 2、A = {150000, 200000, 200000}、B = {150000, 120000, 180000}、C = {210000, 160000, 150000} の場合、出力は 1100000 になります。

このケースでは、価値200000の青い車2台を販売し、さらに価値210000の無彩色の車を青く塗装して販売することで、青い車からの合計収入は610000になります。また、価値180000の赤い車を1台販売し、価値160000と150000の無彩色の車を赤く塗装して販売すれば、合計490000になります。したがって、得られる総利益は 610000 + 490000 = 1100000 となります。

解法のアプローチ

この問題は貪欲法を用いることで効率的に解けます。基本的な考え方は、赤い車と青い車の中から価値の高いものを選び、必要に応じて無彩色の車をより高値となる色に塗装して組み合わせを入れ替えることで、全体の合計額を最大化するというものです。具体的な手順は以下の通りです。

配列dpを定義する
配列A、B、Cを降順にソートする
i := 0 から i < p の間、i を1ずつ増加させながら:
    dpの末尾にA[i]を挿入する
i := 0 から i < q の間、i を1ずつ増加させながら:
    dpの末尾にB[i]を挿入する
配列dpをソートする
配列dpを逆順に並べ替える
i := 1 から i < dpのサイズ の間、i を1ずつ増加させながら:
    dp[i] := dp[i] + dp[i - 1]
tmp := 0
res := dpの最後の要素
i := 1 から i <= min(c, p + q) の間、i を1ずつ増加させながら:
    tmp := tmp + C[i - 1]
    res := max(res, dp[p + q - i] + tmp)
resを返す

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int p, int q, int a, int b, int c, vector<int> A, vector<int> B, vector<int> C){
    vector<int> dp(1, 0);
    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend());
    sort(C.rbegin(), C.rend());
    for(int i = 0; i < p; ++i)
        dp.push_back(A[i]);
    for(int i = 0; i < q; ++i)
        dp.push_back(B[i]);
    sort(dp.begin(), dp.end());
    reverse(dp.begin() + 1, dp.end());
    for(int i = 1; i < (int)dp.size(); ++i)
        dp[i] += dp[i - 1];
    int tmp = 0;
    int res = dp.back();
    for(int i = 1; i <= min(c, p + q); ++i) {
        tmp += C[i - 1];
        res = max(res, dp[p + q - i] + tmp);
    }
    return res;
}
int main() {
    int p = 3, q = 3, a = 3, b = 3, c = 2;
    vector<int> A = {150000, 200000, 200000}, B = {150000, 120000, 180000}, C = {210000, 160000, 150000};
    cout<< solve(p, q, a, b, c, A, B, C);
    return 0;
}

入力

3, 3, 3, 3, 2, {150000, 200000, 200000}, {150000, 120000, 180000}, {210000, 160000, 150000}

出力

1100000