C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++でのパーティションの等しいサブセット和

正の数のみを含む空でない配列があるとすると、両方のサブセットの要素の合計が同じになるように、配列を2つのサブセットに分割できるかどうかを確認する必要があります。したがって、入力が[1,5,11,5]のような場合、出力はtrueになります。この配列は[1、5、5]および[11]

として分割できるため

これを解決するには、次の手順に従います-

  • n：=配列のサイズ
  • 合計：=0
  • for i：=0からn– 1
    • sum：=sum + nums [i]
  • 合計が奇数の場合、falseを返します
  • 合計：=合計/ 2
  • サイズ合計+1のdpという1つの配列を作成します
  • dp [0]：=true
  • 0からn–1の範囲のiの場合
    • x：=nums [i]
    • for j：=合計をj – x
      • dp [j]：=dp[j]またはdp[j--x]、これは0ではありません
  • return dp [sum]
例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canPartition(vector<int>& nums) {
      int n = nums.size();
      int sum = 0;
      for(int i =0;i<n;i++)sum+=nums[i];
      if(sum&1)return false;
      sum/=2;
      vector <bool> dp(sum+1);
      dp[0] = true;
      for(int i =0;i<n;i++){
         int x = nums[i];
         for(int j =sum;j-x>=0;j--){
            dp[j]=dp[j] || dp[j-x];
         }
      }
      return dp[sum];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,11,5};
   cout << ob.canPartition(v);
}

入力

[1,5,11,5]
出力 
1

  1. C++での等しいツリーパーティション

    n個のノードを持つ二分木があるとすると、元のツリーの1つのエッジを削除した後、値の合計が等しい2つのツリーにツリーを分割できるかどうかを確認するタスクがあります。 したがって、入力が次のような場合 そうすれば、出力は真になります。 これを解決するには、次の手順に従います- 1つのスタックstを定義する 関数solve（）を定義します。これはノードを取ります ノードがnullの場合、- 0を返す leftSum：=solve（ノードの左側） rightSum：=solve（ノードの権利） curr：=val + leftSum+rig

  2. C ++でのアリコートの合計？

    ここで、アリコートの合計は何ですか？ nのアリコート和は、nを除くnのすべての完全な因子の合計です。たとえば、数値が20の場合、完全な因数は（1、2、4、5、10）です。したがって、アリコートの合計は22です。 興味深い事実の1つは、ある数のアリコートの合計がその数そのものである場合、その数は完全数であるということです。たとえば、6。係数は（1、2、3）です。アリコートの合計は1+2 + 3=6です。 次のアルゴリズムを使用してアリコートの合計を取得する方法を見てみましょう。 アルゴリズム getAliquotSum（n） begin    sum := 0 &nbs