C++で解くショッピングオファー問題：特別オファーを活用して最安値を求める方法

ある店では複数の商品が販売されており、それぞれの商品には価格が設定されています。しかし、この店には「特別オファー（スペシャルオファー）」と呼ばれる割引セットも存在します。1つの特別オファーは、1種類以上の異なる商品の組み合わせを、まとまった販売価格で提供するものです。

ここで、商品ごとの価格リスト、利用可能な特別オファーの集合、そして各商品について購入する必要のある個数が与えられます。求めるのは、これらの商品をちょうど必要な個数だけ購入するときに支払うべき最低金額です。特別オファーを最適に活用することで、合計額を抑えられる可能性があります。

問題の形式

各特別オファーは配列として表現されます。配列の最後の数値がそのオファーを利用したときに支払う価格を表し、それ以外の数値は、このオファーでそれぞれの商品を何個入手できるかを示します。

具体例

入力が [2,5]、[[3,0,5],[1,2,10]]、[3,2] の場合、出力は 14 になります。この例を詳しく見てみましょう。

• 商品はAとBの2種類あり、価格はそれぞれ2ドルと5ドルです。
• 特別オファー1：3個のAと0個のBを5ドルで購入できます。
• 特別オファー2：1個のAと2個のBを10ドルで購入できます。

必要なのは「Aを3個、Bを2個」なので、まず特別オファー2を使って1個のAと2個のBを10ドルで購入し、残りの2個のAを単品で4ドル（2×2ドル）購入します。合計は 10 + 4 = 14ドル となり、これが最小の支払額です。

解法のアプローチ

この問題は、メモ化（キャッシュ）付きの再帰探索によって効率的に解くことができます。基本的な考え方は次のとおりです。

1. まず、すべての商品を単品価格で購入した場合の合計額を計算します（これが初期の候補）。
2. 次に、各特別オファーについて、必要個数を満たしていれば適用し、残りの必要個数に対して再帰的に同じ処理を行います。
3. すでに計算済みの「必要個数の組み合わせ」はメモに保存しておき、同じ計算を繰り返さないようにします。

アルゴリズムの手順

• 結果をキャッシュするためのマップ memo を定義します。
• 単品購入の合計額を返すメソッド directPurchase() を定義します。引数は価格配列と必要個数配列です。
  • ret := 0 と初期化します。
  • i を 0 から価格配列のサイズ - 1 まで繰り返します。
    • ret := ret + price[i] * needs[i]
  • ret を返します。
• 補助メソッド helper() を定義します。引数は価格配列、特別オファーの行列、必要個数配列、開始インデックスです。
  • memo に needs が存在すれば、memo[needs] を返します。
  • ret := directPurchase(price, needs) とします。
  • i を index から特別オファー行列の行数 - 1 まで繰り返します。
    • j について、needs[j] < special[i][j] ならば ok := false としてループを抜けます。
    • そうでなければ、needs[j] - special[i][j] を一時配列 temp に追加します。
  • ok が true の場合：
    • op1 := special[i] の最後の要素 + helper(price, special, temp, i)
    • ret := min(ret, op1)
  • memo[needs] := ret として保存し、ret を返します。
• メイン処理では、helper(price, special, needs, 0) の結果を返します。

C++による実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map <vector <int> , int> memo;
   int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
      return helper(price, special, needs, 0);
   }
   int helper(vector <int>& price, vector < vector <int> >& special, vector <int>& needs, int idx){
      if(memo.count(needs)) return memo[needs];
      int ret = directPurchase(price, needs);
      for(int i = idx; i < special.size(); i++){
         vector <int> temp;
         bool ok = true;
         for(int j = 0; j < special[i].size() - 1; j++){
            if(needs[j] < special[i][j]) {
               ok = false;
               break;
            }
            temp.push_back(needs[j] - special[i][j]);
         }
         if(ok){
            int op1 = special[i][special[i].size() - 1] + helper(price, special, temp, i);
            ret = min(ret, op1);
         }
      }
      return memo[needs] = ret;
   }
   int directPurchase(vector <int>& price, vector <int>& needs){
      int ret = 0;
      for(int i = 0; i < price.size(); i++){
         ret += price[i] * needs[i];
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {2,5};
   vector<vector<int>> v2 = {{3,0,5},{1,2,10}};
   vector<int> v3 = {3,2};
   Solution ob;
   cout << (ob.shoppingOffers(v1, v2, v3));
}

入力

[2,5]
[[3,0,5],[1,2,10]]
[3,2]

出力

14

まとめ

この問題は、全ての特別オファーの適用パターンを再帰的に試しながら、メモ化によって重複計算を排除することで効率的に最適解を求められます。単品購入をベースラインとし、オファーを適用できるたびに残りの必要個数を更新して再帰的に最小コストを探索する、というシンプルかつ強力な手法です。