기술나눔

【1.5】동적 프로그래밍 - 등합 부분 집합 분할에 대한 솔루션

2024-07-12

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

1. 문제


양의 정수만 포함하는 비어 있지 않은 배열 nums가 제공됩니다. 두 부분 집합의 요소 합계가 동일하도록 이 배열을 두 부분 집합으로 나눌 수 있는지 확인하세요.

2. 솔루션 아이디어 1

동적 프로그래밍 솔루션

이 문제는 역추적 알고리즘을 사용하여 해결할 수 없습니다. 데이터 양이 많으면 시간 초과가 발생합니다. 동적 프로그래밍을 사용할 수 있습니다.
이 질문은 배열을 두 부분으로 나눈 경우 두 부분의 요소 합이 같은지 여부를 결정합니다. 먼저 배열에 있는 모든 요소의 합을 계산한 다음 그 합이 짝수인지 확인해야 합니다. 짝수가 아닌 경우 완전히 동일한 두 부분으로 나눌 수 없다는 의미이며 반환됩니다. 직접적으로 거짓.
짝수인 경우 합이 sum/2와 같은 요소가 있는지 확인하면 됩니다. 즉, 합이 sum/2와 같으면 나머지도 합/2와 같아야 합니다. 배열을 동일한 요소를 가진 두 부분으로 나눌 수 있습니다.
그러면 이때 문제는 매우 명확해집니다. sum/2가 배낭의 용량이라고 가정하면 배낭에 있는 요소의 최대 합이 sum과 같을 경우 일부 요소만 찾아서 배낭에 넣으면 됩니다. /2, 이는 배열을 두 개의 동일한 부분으로 나눌 수 있음을 의미합니다. 이것은 전형적인 0-1 배낭 문제가 아닌가? 일련의 배낭 문제 중 기본적인 배낭 문제에 대한 자세한 내용은 아래에서 읽을 수 있습니다. 여기서는 소개를 반복하지 않겠습니다. 우리는 그의 재귀 공식을 찾고 dp[i][j]를 정의하여 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]；
둘 중 최대값을 취하라

최종 재귀 수식 및 코드는 다음과 같습니다.

  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. }

2차원 배열 dp는 부울 유형입니다. 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차원 배열을 계산할 때 현재 값은 위 행에만 관련되어 있으므로 이를 1차원으로 변경할 수 있습니다. 두 번째 for 루프는 플래시백이어야 합니다. 그렇지 않으면 이전 값을 덮어쓰게 됩니다. 결과가 틀릴 수도 있으니 자세히 살펴보세요.
dp[j] = (dp[j] || dp[j - 숫자 [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 알고리즘 솔루션

각 요소를 선택할 수 있는지 여부만 결정하면 됩니다. 가능한 모든 조합의 요소 합계가 합/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인 비트[sum+1] 배열만 적용하면 됩니다. 배열의 숫자는 0과 1만 될 수 있습니다. 매우 긴 이진 비트라고 생각할 수 있습니다. int 및 long 유형이 너무 짧습니다. 여기서는 배열을 사용하고 있습니다. 그런 다음 배열의 요소(예: m)를 탐색할 때마다 이진 비트가 m 비트만큼 왼쪽으로 이동한 다음 원래 이진 비트와 OR됩니다. 마지막으로 비트[합/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 등 다양한 언어에 능숙하며, 오픈 소스 분야에서 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편