C++で解く「トークンのバッグ」問題：貪欲法による最大スコアの求め方

問題の概要

初期パワー P と初期スコア 0 点を持った状態で、トークンの入った袋が 1 つ与えられます。各トークンには値 token[i] が割り当てられており、それぞれ最大 1 回しか使用できません。トークンの使い方には、次の 2 通りがあります。

• 現在のパワーが token[i] 以上の場合、トークンを表向きにプレイできます。パワーを token[i] 消費し、その代わりにスコアを 1 点獲得します。
• 現在のスコアが 1 点以上ある場合、トークンを裏向きにプレイできます。スコアを 1 点失う代わりに、パワーを token[i] 獲得します。

この問題では、任意の数のトークンを使用した後に到達できる最大スコアを求めます。

たとえば、tokens = [100, 200, 300, 400]、P = 200 という入力が与えられた場合、出力は 2 になります。

解法のアプローチ（貪欲法）

この問題は貪欲法（グリーディ法）を用いることで効率的に解けます。ポイントは次の 2 点です。

• スコアを稼ぎたいときは、コストを抑えるため残っている中で最もパワーの小さいトークンを表向きに使う。
• パワーが不足したときは、少しでも多くのパワーを回収できるよう最もパワーの大きいトークンを裏向きに使う。

具体的な手順は以下のとおりです。

1. n を配列 v のサイズとし、答えとなる ret := 0 で初期化します。
2. 配列 v を昇順にソートします。
3. i := 0（最小側のインデックス）、j := n − 1（最大側のインデックス）、curr := 0（現在のスコア）とします。
4. i ≤ j かつ x ≥ v[i] である限り、以下を繰り返します。
   • x ≥ v[i] の間、v[i] を表向きにプレイします（x から v[i] を減算し、curr と i をそれぞれ 1 増やす）。
   • ret を max(curr, ret) で更新します。
   • j ≥ i かつ curr ≠ 0 かつ x < v[i] の間、v[j] を裏向きにプレイします（x に v[j] を加算し、curr と j をそれぞれ 1 減らす）。
5. 最後に ret を返します。

それでは、以下の実装例を見ながら理解を深めていきましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int bagOfTokensScore(vector<int>& v, int x) {
      int n = v.size();
      int ret = 0;
      sort(v.begin(), v.end());
      int i = 0;
      int j = n - 1;
      int curr = 0;
      while(i <= j && x >= v[i]){
         while(i <= j && x >= v[i]){
            x -= v[i];
            curr++;
            i++;
         }
         ret = max(curr, ret);
         while(j >= i && curr && x < v[i]){
            curr--;
            x += v[j];
            j--;
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {100,200,300,400};
   Solution ob;
   cout << (ob.bagOfTokensScore(v1, 200));
}

入力

[100,200,300,400]
200

出力

2