← 完整题目索引

PROJECT EULER · #0103

特殊子集和:最优

Special Subset Sums: Optimum

仅题目 · 已解决原题 ↗

S(A) 表示集合 A 中大小为 n 的元素之和。如果对于任何两个非空不相交子集 BC,以下属性为真,我们将其称为特殊和集:

  1. S(B)S(C);即子集之和不能相等。
  2. 如果 B 包含的元素多于 C,则 S(B)>S(C)

如果对于给定的n最小化S(A),我们将其称为最优特殊和集。下面给出前五个最佳特殊和集。

  • n=1: {1}
  • n=2: {1,2}
  • n=3: {2,3,4}
  • n=4: {3,5,6,7}
  • n=5: {6,9,11,12,13}

似乎对于给定的最优集 A={a1,a2,,an},下一个最优集的形式为 B={b,a1+b,a2+b,,an+b},其中 b 是上一行的"中间"元素。

通过应用此"规则",我们预计 n=6 的最佳设置为 A={11,17,20,22,23,24},其中 S(A)=117。然而,这不是最优集,因为我们仅仅应用了一种算法来提供接近最优集。 n=6 的最佳设置为 A={11,18,19,20,22,25},其中 S(A)=115 和相应的设置字符串:111819202225。

鉴于 An=7 的最优特殊和集,求其集合字符串。

注意:此问题与问题 105问题 106 相关。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。