技術共有

【1.5】動的計画法 - 等和サブセット分割の解法

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. 問題点


正の整数のみを含む空ではない配列 nums が与えられます。 2 つのサブセットの要素の合計が等しくなるように、この配列を 2 つのサブセットに分割できるかどうかを判断してください。

2. 解決策のアイデア 1

ダイナミックプログラミングソリューション

データ量が大きい場合、バックトラッキング アルゴリズムを使用してこの問題を解決することはできません。動的プログラミングを使用できます。
この質問は、配列が 2 つの部分に分割されたときに、2 つの部分の要素の合計が等しいかどうかを判断します。まず、配列内のすべての要素の合計を計算し、その合計が偶数であるかどうかを判断する必要があります。偶数でない場合は、完全に等しい 2 つの部分に分割できないことを意味し、次の結果が返されます。直接的には false です。
偶数の場合は、合計が sum/2 に等しい要素がいくつかあるかどうかを判断するだけで済みます。要素が sum/2 に等しい場合、残りも sum/2 に等しい必要があります。これは、次のことを意味します。配列を等しい要素を持つ 2 つの部分に分割できます。
現時点での問題は非常に明確です。sum/2 がバックパックの容量であると仮定すると、バックパック内の要素の最大合計が sum に等しい場合に、いくつかの要素を見つけてバックパックに入れるだけで済みます。 /2 は、配列 Divide を 2 つの等しい部分に分割できることを意味します。これは古典的な 0-1 ナップサック問題ではないでしょうか?一連のナップサック問題の基本的なナップサック問題については、ここでは繰り返し説明しません。私たちは、容量 j のバックパックに i 番目のアイテムを入れることによって得られる最大値を表す dp[i][j] を定義する彼の再帰式を探しています。
i 番目の項目の値は nums [i -1] です。
nums [i -1]>j の場合、バックパックの容量が足りなくて i 番目のアイテムが入らないため、i 番目のアイテムを選択できないことを意味します。
dp[i][j]=dp[i -1][j]；
nums [i -1]<=j の場合、j 番目のアイテムをバックパックに入れるかどうかを選択できます。入れる場合は最大値を取得します。バックパックの容量は最大値です。
dp[i][j]=dp[i-1][j-数値[i-1]]+数値[i-1]
手放さないと
dp[i][j]=dp[i -1][j]；
2 つの最大値を取る

最終的な再帰式とコードは次のとおりです。

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
  17.     for (int i = 1; i <= length; ++i) {
  18.         for (int j = 1; j <= target; ++j) {
  19.             // 下面是递推公式
  20.             if (j >= nums[i - 1]) {
  21.                 dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
  22.             } else {
  23.                 dp[i][j] = dp[i - 1][j];
  24.             }
  25.         }
  26.     }
  27.     // 判断背包最大是否能存放和为target的元素
  28.     return dp[length][target] == target;
  29. }

このように書くこともできます。 dp[i][j] は、配列内の最初の i 要素の合計が j の合計を形成できるかどうかを示します。 0]=true。これは、最初の 0 要素 (つまり、要素なし) は合計 0 を形成できることを意味します。コードは以下のように表示されます

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2得到target
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
  17.     // base case
  18.     dp[0][0] = true;
  19.     for (int i = 1; i <= length; ++i) {
  20.         for (int j = 0; j <= target; ++j) {
  21.             // 递推公式
  22.             if (j >= nums[i - 1]) {
  23.                 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
  24.             } else {
  25.                 dp[i][j] = dp[i - 1][j];
  26.             }
  27.         }
  28.     }
  29.     // 返回能否找到和为target的子集
  30.     return dp[length][target];
  31. }

上記の 2 次元配列を計算する場合、現在の値は上の行にのみ関連していることがわかります。そのため、2 番目の for ループをフラッシュバックする必要があることに注意してください。フラッシュバックしないと、前の値が上書きされます。結果は間違っているので、よく見てください。
dp[j] = (dp[j] || dp[j - nums [i - 1]]);
同じ行の末尾の値が前の値に依存していることがわかります。フラッシュバックでない場合は、前の値が変更され、後の値の計算でエラーが発生します。コードを見てみましょう

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2得到target
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<bool> dp(target + 1, false);
  17.     // base case
  18.     dp[0] = true;
  19.     for (int i = 0; i < length; ++i) {
  20.         // 注意这里j要倒序
  21.         for (int j = target; j >= nums[i]; --j) {
  22.             // 递推公式
  23.             dp[j] = dp[j] || dp[j - nums[i]];
  24.         }
  25.     }
  26.     // 返回能否找到和为target的子集
  27.     return dp[target];
  28. }

3. 解決策のアイデア 2

DFS アルゴリズム ソリューション

各要素を選択するかどうかは、すべての可能な組み合わせの要素の合計が sum/2 に等しいかどうかを判断するだけで済みます。左側の子ノードは、その要素の選択を表すと考えることができます。下の図に示すように、右側の子ノードは現在の要素が選択されていることを示し、オレンジ色のノードは現在の要素が選択されていることを示します。現在の要素が選択されていないことを示します。

まずは暫定的な実装コードを見てみましょう

  1. #include <vector>
  2.  
  3. bool dfs(const std::vector<int>& nums, int target, int index) {
  4.     // target等于0，说明存在一些元素的和等于sum/2，直接返回true
  5.     if (target == 0) return true;
  6.     // 如果数组元素都找完了，或者target小于0，直接返回false
  7.     if (index == nums.size() || target < 0) return false;
  8.     // 选择当前元素和不选择当前元素两种情况
  9.     return dfs(nums, target - nums[index], index + 1) || dfs(nums, target, index + 1);
  10. }
  11.  
  12. bool canPartition(std::vector<int>& nums) {
  13.     // 计算数组中所有元素的和
  14.     int sum = 0;
  15.     for (int num : nums) sum += num;
  16.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  17.     if ((sum & 1) == 1) return false;
  18.     // 调用dfs函数
  19.     return dfs(nums, sum >> 1, 0);
  20. }

ただし、残念ながら計算量が多すぎるため、操作がタイムアウトしてしまいます。最適化してコードを確認してください。

  1. #include <vector>
  2.  
  3. bool dfs(const std::vector<int>& nums, int index, int target, std::vector<std::vector<int>>& map) {
  4.     // target等于0，说明存在一些元素的和等于sum/2，直接返回true
  5.     if (target == 0) return true;
  6.     // 如果数组元素都找完了，或者target小于0，直接返回false
  7.     if (index >= nums.size() || target < 0) return false;
  8.     // 如果此子问题已经被计算过，直接返回结果
  9.     if (map[index][target] != -1) return map[index][target] == 1;
  10.     // 选择当前元素
  11.     bool select = dfs(nums, index + 1, target - nums[index], map);
  12.     // 不选择当前元素
  13.     bool unSelect = dfs(nums, index + 1, target, map);
  14.     // 存储结果，并返回
  15.     map[index][target] = select || unSelect ? 1 : 0;
  16.     return select || unSelect;
  17. }
  18.  
  19. bool canPartition(std::vector<int>& nums) {
  20.     // 计算数组中所有元素的和
  21.     int sum = 0;
  22.     for (int num : nums) sum += num;
  23.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  24.     if (sum % 2 != 0) return false;
  25.     // sum除以2
  26.     int target = sum / 2;
  27.     std::vector<std::vector<int>> map(nums.size(), std::vector<int>(target + 1, -1));
  28.     return dfs(nums, 0, target, map);
  29. }

4. 解決策のアイデア 3

ビット演算ソリューション

ここではビット演算を使用できますが、重要なのは、正の整数の空でない配列、各配列の要素が 100 を超えないこと、配列のサイズが 200 を超えないことなど、質問内のいくつかの制限にあります。 。
原理は非常に単純です。サイズ sum+1 の配列 bits[sum+1] を適用するだけです。配列内の数値は 0 と 1 のみです。これは非常に長いバイナリ ビットであると考えることができます。 int と long 型は短すぎるため、ここでは配列を使用しています。次に、配列内の要素 (m など) がトラバースされるたびに、バイナリ ビットが m ビット左にシフトされ、元のバイナリ ビットと OR が計算されます。最後に、bits[sum/2] が 1 かどうかを判断し、1 の場合は true を返します。テキストの説明はあまり単純ではありません。例 1 を例として図を描いてみましょう。

最後に、最終的な演算結果が 1 である限り、配列内の要素を使用して結合することができ、それが 0 である限り、配列内の要素を使用して結合することはできないというルールがわかります。以上の手順でコードを書くのは簡単です。バイナリ ビットの中間値が 1 であるかどうかを判断するだけでよいため、計算する必要があるのは下位ビットだけであり、上位ビットは左に移動されるため計算する必要はまったくありません。 bit は中間値に影響を与えないので、ここで実行できます。少し最適化して、最後にコードを見てみましょう。

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有数字的和
  5.     int sum = 0;
  6.     for (int n : nums) {
  7.         sum += n;
  8.     }
  9.     // 如果sum是奇数，直接返回false
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     int len = sum / 2;
  14.     // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
  15.     std::vector<char> bits(len + 1, 0);
  16.     bits[0] = 1;
  17.     for (int num : nums) {
  18.         for (int j = len - num; j >= 0; j--) {
  19.             bits[j + num] |= bits[j];
  20.         }
  21.         // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
  22.         if ((bits[len] & 1) != 0) {
  23.             return true;
  24.         }
  25.     }
  26.     return false;
  27. }

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

プライベートな連絡先の最初の情報

送料