C++の家から盗まれた可能性のある最大の価値を見つける

この問題では、いくつかの値を持つn個の家が与えられます。私たちの仕事は、家から盗まれた可能性のある最大の価値を見つけることです。

問題の説明 −各家にある値で構成される配列houses[]があります。泥棒は家を奪いますが、隣人が盗難について知っているので、彼は隣接する2つの家から盗むことはできません。泥棒が家から捕まることなく盗むことができる最大の価値を見つける必要があります。

問題を理解するために例を見てみましょう

入力

houses[] = {5, 2, 1, 6, 7, 9, 4, 3}

出力

23

説明

The max values can be stolen as : 5, 6, 9, 3.

ソリューションアプローチ

問題の解決策は、動的計画法を使用して見つけることができます。泥棒がインデックスiの家から盗んだ場合、インデックス（i + 1）の家から盗むことができないように、泥棒が盗んだ最大値を見つける必要があるためです。また、インデックス（i-1）の家からは盗まれなかったでしょう。この問題を解決するために、サイズnのDP配列を作成します。また、基本ケースでは、DP[0]をhouses[0]で初期化し、DP[1]をhouses[1]で初期化します。次に、インデックス2からn-1までのDPのすべての値を見つけます。 DP [i]の値は、DP [i-2] +house[i]またはDP[i-1]の最大値になります。そして最後に、DPアレイの最後の値は、盗まれる可能性のある最大値です。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
int calMax(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxValuesStolen(int houses[], int n) {
   if (n == 0)
      return 0;
   int DP[n];
   DP[0] = houses[0];
   DP[1] = calMax(houses[0], houses[1]);
   for (int i = 2; i<n; i++)
      DP[i] = calMax( (houses[i] + DP[i-2]), DP[i-1]);
   return DP[n-1];
}
int main() {
   int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
   int n = sizeof(houses)/sizeof(houses[0]);
   cout<<"The maximum possible values stolen from the houses is
   "<<findMaxValuesStolen(houses, n);
   return 0;
}

出力

The maximum possible values stolen from the houses is 23

このソリューションは優れていますが、盗まれた最大値は2つの値のみを使用して検出できるという事実を使用して、より効率的にすることができます。 DPと同様に、各インデックスに2つの値のみを使用しました。したがって、2つの変数のみを使用して、問題に対するスペースの複雑さを軽減する解決策を見つけることができます。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
int calMax(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxValuesStolen(int houses[], int n) {
   if (n == 0)
      return 0;
   int maxValStolen;
   int val1 = houses[0];
   int val2 = calMax(houses[0], houses[1]);
   for (int i = 2; i<n; i++) {
      maxValStolen = calMax( (houses[i]+val1) , val2);
      val1 = val2;
      val2 = maxValStolen;
   }
   return maxValStolen;
}
int main() {
   int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
   int n = sizeof(houses)/sizeof(houses[0]);
   cout<<"The maximum possible values stolen from the houses is "<<findMaxValuesStolen(houses, n);
   return 0;
}

出力

The maximum possible values stolen from the houses is 23