Обмен технологиями

【1.5】Динамическое программирование – решение для разделения подмножеств с равной суммой

2024-07-12

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

1. Проблема


Вам дан непустой массив nums, содержащий только положительные целые числа. Оцените, можно ли этот массив разделить на два подмножества так, чтобы сумма элементов двух подмножеств была равна.

2. Идея решения 1

Решение для динамического программирования

Эту проблему невозможно решить с помощью алгоритма обратного отслеживания. Если объем данных велик, время ожидания истекает. Мы можем использовать динамическое программирование.
Этот вопрос определяет, равна ли сумма элементов двух частей, когда массив разделен на две части. Сначала нам нужно вычислить сумму всех элементов массива, а затем определить, является ли сумма четным числом: если это не четное число, значит, ее нельзя разделить на две совершенно равные части, и она вернется ложь напрямую.
Если это четное число, нам нужно только определить, есть ли элементы, сумма которых равна сумме/2. Если оно равно сумме/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. }

Мы также можем написать так: Двумерный массив 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. }

Мы видим, что при вычислении приведенного выше двумерного массива текущее значение связано только с указанной выше строкой, поэтому мы можем изменить его на одномерное. Обратите внимание, что второй цикл 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 и т.д. .
Принцип очень прост: нам нужно применить только массив bits[sum+1] размера sum+1. Числа в массиве могут быть только 0 и 1. Мы можем представить его как очень длинный двоичный бит, потому что. int и тип long слишком короткий, здесь мы используем массив. Затем каждый раз, когда просматривается элемент массива, например m, двоичный бит сдвигается влево на m бит, а затем выполняется операция ИЛИ с исходным двоичным битом. Наконец, определите, равно ли bits[sum/2] 1, и верните true, если оно равно 1.Текстовое описание не очень простое. Давайте возьмем Пример 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 и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта