C++で合計が等しい2つのセットの最大合計を見つけるプログラム

numsと呼ばれる数値のリストがあるとします。ここで、合計が同じで最大である2つのセットを見つけてから、合計値を見つけます。

したがって、入力がnums =[2、5、4、6]の場合、セットは[2、4]と[6]であるため、出力は6になります。

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

• 合計：=0
• numsの各数値iについて、
  • sum：=sum + i
• n：=numsのサイズ
• サイズ（n + 1）x（2*合計+5）の2D配列dpを1つ定義し、-1で埋めます
• dp [0、sum]：=0
• iを初期化する場合：=1、i <=nの場合、更新（iを1つ増やす）、実行-
  • x：=nums [i-1]
  • jを初期化する場合：=0、j <2 * sum + 5の場合、更新（jを1増やす）、実行-
    • j --x> =0で、dp [i -1、j --x]が-1に等しくない場合、^ −
      • dp [i、j]：=最大dp [i、j]および（dp [i-1、j-x] + x）
    • j + x <（2 * sum + 5）であり、dp [i-1、j + x]が-1に等しくない場合、-
      • dp [i、j]：=最大dp [i、j]および（dp [i-1、j + x]）
    • dp [i、j]：=最大dp [i、j]およびdp [i-1、j]
• return dp [n、sum]

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int sum = 0;
      for (int i : nums) sum += i;
      int n = nums.size();
      vector<vector<int> > dp(n + 1, vector<int>(2 * sum + 5, -1));
      dp[0][sum] = 0;
      for (int i = 1; i <= n; i++) {
         int x = nums[i - 1];
         for (int j = 0; j < 2 * sum + 5; j++) {
            if (j - x >= 0 && dp[i - 1][j - x] != -1) {
               dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + x);
            }
            if (j + x < 2 * sum + 5 && dp[i - 1][j + x] != -1) {
               dp[i][j] = max(dp[i][j], dp[i - 1][j + x]);
            }
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
         }
      }
      return dp[n][sum];
   }
};
int solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
main(){
   vector<int> v = {2, 5, 4, 6};
   cout << solve(v);
}

入力

{2, 5, 4, 6}

出力

6