Technology sharing

1.5】Dynamic Programming-Solutio ad Partes Aequalis Summa Subsets

2024-07-12

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

1. Problema


Nummi ordinati non-vacui dati es in quibus integri tantum positivi sunt. Quaeso diiudica, num hic ordo in duo subsellia dividi possit ut summa elementorum duorum copiarum aequalis sit.

2. Solutio idea 1

Dynamic programmatio solutionis

Hoc problema solvendum non potest per recessum algorithm. Uti possumus programmatibus dynamicis.
Haec quaestio determinat utrum summa elementorum duarum partium sit aequalis quando ordinata dividitur in duas partes. Primum omnium elementorum summam computare oportet in ordine, deinde utrum summa sit par numerus: si non est numerus par, non potest dividi in duas partes omnino aequales, et revertetur. falsum directe.
Si numerus par sit, tantum determinare oportet an elementa sint quorum summa summa/2 sit aequalis aciem in duas partes aequalibus dividere possumus.
Tunc problema perlucet hoc tempore. Posito summa/2 capacitas manticae, tantum opus est elementa quaedam invenire et ea in mantica ponere 2, significat quod ordinata dividere possumus in duas partes aequales. Estne haec res classica 0-1 peram problema? Peram quaestionem fundamentalem in serie peram problematum infra pro singulis legi potest. Eius recursionis formulam quaerimus et definimus dp[i][j] valorem maximum consecutum, ponendo i-th item in mantica cum capacitate j.
Valor i-th item est nums [i -1];
Si nums [i -1]>j, significat manticam capacitatem non satis esse et i-th item poni non posse, ut i-th item, tum
dp[i][j]=dp[i -1][j]；
Si nums [i -1]<=j, significat eum in mantica ponere posse MANTICA facultatem
dp[i][j]=dp[i-1][j-nums[i-1]]+nums[i-1]
Si non dimittet
dp[i][j]=dp[i -1][j]；
Accipere maximam duorum

Postrema formula recursiva et in codice haec sunt:

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

Etiam hoc modo scribere possumus. Duo dimensiva ordinata dp generis boolean. 0]=verum, quod significat Prima 0 elementa (id est nulla elementa) summam 0 formare potest.ut infra ostende codice

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

Videmus quod cum supra duos dimensiva ordinata computando, valorem currentem tantum ad supra ordinem relatum est, ut ad unum dimensivum mutare possumus et fiet iniuria, vide propius
dp[j] = (dp[j] dp[j - nums [i - 1]]);
Intelligere potes valorem in fine eiusdem lineae a priori dependeat. Si flashback non est, prior valor modificatur, qui errorem in calculi posterioris causa faciet.Vide in codice fiat scriptor

  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. Solutio idea 2

DFS algorithmus solution

Unumquodque elementum seligi potest necne. Tantum opus est determinare utrum summa elementorum in omnibus suis combinationibus possibilibus aequalis sit summa/2 Praesens elementum, et nodi ius infantis electionem currentis elementi repraesentat. Nodus puer indicat elementum currente non delectum, ut in figura infra ostenditur indicat hodiernam elementum non lectus.

Inspice exsecutionem Codicis praeviam primum

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

Sed proh dolor, quia moles calculi nimis magna est, operandi tempus ex causa faciet.

  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. Solutio idea 3

Bit operatio solution

Aliquantulus operationes hic adhiberi possunt, sed clavis in aliquibus restrictionibus in quaestione posita est, ut non-vacua ordinata positivorum integris, elementa in unaquaque ordinata non excedant 100, magnitudo ordinata non excedat 200, etc. .
Principium valde simplex est. Tantum opus est pro summae magnitudinis frenis ordinatis++ int et Longum genus nimis breve est, hic acie utimur. Quotiescumque elementum in ordine percurritur, ut m, frenum binarium ad laevam per m frenos transfertur et deinde ORed cum bit in originali binario. Denique discerne an frusta[sum/2] sit 1 , et vera redde si est 1 .Textus descriptio non admodum aperta est. Exemplum 1 ut exemplum picturae sumamus.

Denique regulam invenies, id est, quamdiu operatio finalis est 1 , potest componi utens elementa in ordine supra processum. Quia tantum opus est determinare utrum medium valorem in bis binarii 1 sit, tantum opus est humilem partem computare, et altitudinis paulum computari omnino non oportet, quia movetur ad sinistram, et alte. frenum non habebit momentum in medio valore, ideo hic facere possumus Paulum ipsum, et tandem codicem inspiciamus.

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

Personal profile

technologiae technologiae plus quam 30 annos operam dedit et in variis linguis proficit ut java, linux, javascript, php, css, etc. Multas contributiones in aperto fonte campo fecit elit documentorum statione ad communicandas quaestiones in technologia progressus ad futuram referentiam

mihi contactus notitia

Mail