此题大多数人的算法是：
用F[i,j]表示，已经选择i个人，差值之和为j，最大的和值之和
枚举嵌套顺序是，已经选择多少人->此次选择哪个人->差值之和

这样会出现的问题是，用同一人重复更新，即F[i,j]的最优解对应的路径已经包括陪审员k，还要用F[i,j]加上陪审员k去转移到下一个状态。

为了解决这个问题，算法加上了验证F[i,j]的路径中是否含有k的步骤，一些程序使用二进制压缩表示来验证，本质是相同的。

但是，这样的修修补补是否保证正确呢？如果答案是某个F[i,j]加上陪审员k构成的，但F[i,j]的最优解已经包括陪审员k，答案应当是F[i,j]的次优解加上陪审员k，这种情况就无法求出答案了。去除了后效性，是不是还能够保证最优子结构性质？

也许有人解释说：背包问题与取物次序无关，但这毕竟不是简单的一维背包问题。我无法构造出上述的数据，因此我猜想这种情况根本不存在，但不知是否能够严格证明，或者指出我上述思路的错误性。

• Re:对标准算法提出的怀疑 (202) chineshboy 2011-07-31 01:35:58
  • Re:对标准算法提出的怀疑 (19) chineshboy 2011-09-09 19:20:53
  • Re:对标准算法提出的怀疑 (287) cyker 2012-06-11 04:40:43
• Re:对标准算法提出的怀疑 (50) WinterWingC 2011-09-07 20:38:58
  • Orz WW~ (54) xuhaoran510 2011-09-07 20:44:59
    • Re:Orz WW~ (14) WinterWingC 2011-09-07 21:14:59
  • Re:对标准算法提出的怀疑 (54) NJUT1401140226 2016-07-24 08:32:34
    • Re:对标准算法提出的怀疑 (120) NJUT1401140226 2016-07-24 08:35:47
• Re:对标准算法提出的怀疑 (142) mickeyandkaka 2012-02-14 19:17:58
• Re:对标准算法提出的怀疑 (2110) 1120121860 2013-07-17 17:09:59
• 尝试解释这个BUG (509) haqishen 2015-02-07 13:03:16