1. 概要

コンピュータサイエンスでよく知られている問題の1つは、目標数を超えずに、目標数に最も近い数のサブセットを見つけることです。

このチュートリアルでは、問題のさまざまなバージョンについて説明し、いくつかの解決策を提供し、各バージョンの解決策を比較します。

2. 問題の定義

この問題では、サイズとターゲット数の整数の配列が与えられます。 配列から、ターゲット数を超えずに、可能な限りターゲット数に近い数のサブセットを見つける必要があります。

この問題には2つのバージョンがあります。 最初のバージョンでは、選択できるアイテムの数が指定されていません。 したがって、合計が可能な限り大きい限り、を超えずに、必要な数のアイテムを選択できます。

ただし、2番目のバージョンのでは、問題は、取得できる値の正確な数を指定します、それを呼び出しましょう。 したがって、配列から正確に値を選択する必要があり、それらの合計も超えないように可能な限り大きくする必要があります。

2つのバージョンのそれぞれについて3つのソリューションについて説明します。

3. 任意の数の要素を選択する

最初のバージョンでは、必要な数のアイテムを選択できます。 唯一の条件は、それらの合計がを超えないように可能な限り大きくなければならないということです。

これを行うには、3つのソリューションがあります。 最初の解決策は、可能なすべてのオプションを試して数値を選択するバックトラッキングソリューションです。 一方、2番目のソリューションは、バックトラッキングソリューションに基づく動的プログラミングアプローチです。

最後に、3番目のソリューションは、バックトラッキングソリューションの改善であるミートインザミドルアプローチです。

3.1. バックトラッキングアプローチ

任意の数のアイテムを選択できる場合の問題のバックトラックソリューションを見てみましょう。

バックトラッキング関数は、現在の数値と現在の合計をパラメーターとして受け取ります。 まず、停止条件について説明します。 目標数よりも大きい合計に達した場合は、無効な結果を示すゼロを返すだけです。

一方、現在のインデックスが配列の範囲外になった場合は、配列全体のウォークを終了したことを意味し、達成できた合計を返すだけです。

次に、現在の番号に対して実行できる両方のオプションを試します。 最初のオプションは、現在の番号を選択することです。 したがって、次の番号を再帰的に呼び出して、合計を更新します。

2番目のオプションは、現在のアイテムを残すことです。 したがって、現在の合計を更新せずに、次の呼び出しを再帰的に呼び出します。

これらの呼び出しのそれぞれは、それが見つけた最良の答えを返します。 結果として、これら2つの値の間の最大値を返す必要があります。

各アイテムから2つの再帰呼び出しを行うため、バックトラッキングアプローチの複雑さはです。ここで、はアイテムの数です。

3.2. 動的計画法アプローチ

動的計画法のアプローチは、バックトラッキングアプローチに対するメモ化です。 動的計画法アプローチの実装を見てみましょう。

まず、配列を定義しましょう。 すでに合計がに等しい場合、範囲のベストアンサーを格納すると想定します。 これに基づいて、動的計画法ソリューションを構築できます。

最初に、基本ケースについて説明します。 現在のインデックスが配列の最後に達した場合は、持っているものを格納する必要があります。

次に、考えられるすべてのインデックスと、達成できるすべての合計を繰り返し処理します。 バックトラッキングアプローチと同様に、インデックスにあり、合計がに等しい状態には2つの選択肢があります。

最初の選択肢は、可能であれば現在の番号を選択することです。 したがって、状態から最良の答えを得ることができます。 2番目の選択肢は、現在の番号を残すことです。 したがって、状態から最良の答えが得られます。

ネストされた2つのforループは、逆方向に反復するように設定されていることに注意してください。 これは、状態が状態の値に依存するためです。 したがって、状態は状態の前に計算する必要があります。 同じことがの状態にも当てはまります。

これらのオプションの両方から、現在の状態でそれらの間の最大値を保存します。 結果として、問題全体に対する答えである合計がゼロに等しい範囲に対する答えが含まれているため、最終的な答えは内部になります。

動的計画法アプローチの複雑さはです。ここで、は要素の数、はターゲットの数です。

3.3. 真ん中のアプローチで会う

バックトラッキングアプローチの複雑さを軽減する、ミートインザミドルアプローチと呼ばれる新しいソリューションを考え出すことができます。 このアプローチの実装を見てみましょう。

この関数は、位置で始まり、位置で終わり、指定されたから始まる配列から、可能なすべての合計の組み合わせを生成します。

この関数の考え方は、バックトラッキングアプローチに似ています。 アイテムごとに、選択するか、残すかを選択できます。 最後に、達成した合計を返します。 この関数は、を超えないすべての合計のリストを返します。

次に、この関数を呼び出して、配列の前半と配列の後半の可能なすべての合計を生成します。

その後、後半の配列を並べ替えます。

さて、主なアイデアは、前半の合計を繰り返すことです。 現在の合計がであると仮定します。 この場合、到達するために必要な最適な値はです。 したがって、2番目のリストに対して二分探索操作を実行して、。以下の最大数を見つけます。 値よりも小さい値がない場合、関数はゼロを返すと想定します。

すべての回答が。よりも小さいことが保証されるため、考えられるすべての回答から最大のものを選択します。

ミートインザミドルアプローチの複雑さはです。ここで、はアイテムの数です。 この複雑さの理由は、です。

3.4. 繰り返しのある要素をいくつでも選択する

問題の別のバージョンでは、繰り返しで目標数になる数のサブセットの最大合計を要求する場合があります。 つまり、同じアイテムを複数回選択できるということです。

この場合、以前のアプローチに対して1つの小さな更新を実行する必要があります。 バックトラッキングと動的計画法のアプローチの場合、ピックオプションを実行すると、インデックスのある次の番号に移動する代わりに、現在の番号に留まります。 したがって、現在の値の繰り返しを許可します。

ミートインザミドルアプローチの場合、検索手法を変更する必要はありません。 ただし、関数を更新する必要があります。 ピックオプションを実行すると、次の番号に移動する代わりに、現在の番号に留まります。

その結果、現在の値を複数回繰り返すことができます。

3.5. 比較

議論されたアプローチ間の比較を提供しましょう：

動的計画法は、複雑さが最も少ない最良のソリューションのように聞こえるかもしれません。 ただし、動的計画法ソリューションはに関連していることに注意してください。 一方、バックトラックとミートインザミドルアプローチはに関連していません。

の値が大きい場合は、バックトラックとミートインザミドルアプローチの方が適しています。 逆に、の値が小さい場合は、動的計画法のアプローチがより適切なオプションと見なされます。

4. 特定の数の要素を選択する

問題の2番目のバージョンでは、合計がそれを超えないように可能な限り近い数を正確に選択するように求められます。

このバージョンでは、3つの可能な解決策があります。 これらのソリューションは、セクション3.1、3.2、および3.3のアプローチを更新したものです。

4.1. バックトラッキングアプローチ

バックトラッキングアプローチの実装を見てみましょう。

このバックトラッキングアプローチは、セクション3.1で提供されているものと似ています。 唯一の違いは、これまでに取得したアイテムの数を表す、も渡す必要があることです。

最初に、停止条件について説明します。 合計がを超える場合、または取得したアイテムの数がを超える場合は、無効な回答を示すゼロを返します。

対照的に、配列の最後に到達すると、の値をチェックします。 配列をウォークスルーして数値を取得できた場合は、達成した合計を返します。 一方、取得したアイテムの数が、未満の場合は、ゼロを返します。

その後、2つのオプションがあります。 現在の番号を選択し、現在の番号を合計に加算して1つ取得した番号の数を増やした後、次の番号を再帰的に呼び出します。 もう1つの選択肢は、現在の要素をそのままにして、との値を変更せずに次の要素に対して再帰呼び出しを実行することです。

これらの両方のオプションから、達成した最大値を返します。

バックトラッキングアプローチの複雑さはです。ここで、はアイテムの数です。

4.2. 動的計画法アプローチ

動的計画法のアプローチも、セクション3.2で提供されているものと同様です。 その実装を見てみましょう：

これまでに取得したアイテムの数を表す新しいディメンションを配列に追加します。 したがって、は、すでに取得された合計がに等しい範囲内の数値のベストアンサーを格納し、これまでに取得された値の数はです。

このアプローチの基本的なケースは、アレイの最後に到達することです。 したがって、取得される要素の数がに等しい場合、答えはこれまでに累積された合計に等しくなります。 それ以外の場合、答えはゼロになります。

その後、、、、およびのすべての可能な組み合わせを繰り返し処理します。 最初のオプションは、可能であれば現在の値を選択することです。 したがって、現在の要素を合計に加算し、取得するアイテムの数を1つ増やした後、次の要素に対応する状態の答えを取得します。

同様に、 2番目のオプションは、現在の値を残すことです。 したがって、との値を変更せずに、次の状態に対応する状態の答えを取得します。

最後に、値の合計と数がゼロに等しい範囲に対応するため、値を返します。

動的計画法アプローチの複雑さはです。ここで、はアイテムの数、はターゲットの数、は選択するアイテムの数です。

4.3. ミートインザミドルアプローチ

特定の数の要素を選択する際の、中間のアプローチを見てみましょう。

この考え方は、セクション3.3で示したものと似ています。 この場合、関数は取得したアイテムの数も取得します。 結果を返すとき、配列は2D配列（または map ）になり、選択した要素の数に対応するセル内に到達した合計を格納します。

セクション3.3のアプローチに対するもう1つの更新は、のすべての値を反復処理する必要があることです。 値を検索するときは、セル内で検索します。 その理由は、配列の前半からアイテムを選択したためです。 したがって、後半から値を選択する必要があります。

ミートインザミドルアプローチの複雑さはです。ここで、はアイテムの数であり、は選択するアイテムの数です。 その理由は、考えられるすべての値を反復処理しているためです。 最悪の場合、合計で値を持つことができます。 また、 。

4.4. 繰り返しのある特定の数の要素の選択

番号の繰り返しを許可する場合、更新はセクション3.4で説明したものと同様です。 バックトラッキング、動的計画法、および中間計画法の選択オプションは、次の番号を移動するのではなく、現在の番号にとどまり、繰り返すことができるようにする必要があります。

4.5. 比較

議論されたアプローチ間の比較を見てください：

5. 結論

このチュートリアルでは、目標数を超えずに可能な限り目標数に近い数のサブセットを選択する問題について説明しました。 問題の2つのバージョンのそれぞれについて3つの解決策について説明しました。

また、各バージョンの3つのアプローチの比較を示しました。