C++에서 합이 같은 두 집합의 최대 합을 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있다고 가정하고 이제 합이 동일하고 최대인 두 집합을 찾은 다음 합 값을 찾습니다.

따라서 입력이 nums =[2, 5, 4, 6]과 같으면 세트가 [2, 4] 및 [6]이므로 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

합계 :=0
num의 각 숫자 i에 대해 다음을 수행합니다.
- 합계 :=합 + i
n :=숫자 크기
(n + 1) x (2 * sum + 5) 크기의 2D 배열 dp 하나를 정의하고 -1로 채움
dp[0, 합계] :=0
초기화 i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), 수행 -
- x :=숫자[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]의 최대값
dp[n, 합계]를 반환

예시(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}