python - 奇偶校验子集和动态规划 Python 解决方案

Question

作为作业给出了这个问题：考虑子集和问题的以下变体。给您正整数 (a1, . . . , an) 以及目标值t。你要设计一个有效的算法来确定是否存在子集 I ⊆ {1, . . . , n}，使得 (a) |I| 是偶数，并且 (b) P i∈I ai = t。

你的算法应该在 O(nt) 时间内运行。注意：这与通常的子集和问题相同，只是现在我们要求子集的基数是偶数。

我目前正在尝试通过调整要保存的备忘录值和同时具有even子集和布尔值和布尔值的对象来应用动态编程子集和解决方案odd。我想我得到了正确的答案，但我确信必须有一种更有创意/更有效的方法来解决它。

有任何想法吗？

标签： pythonalgorithmdynamic-programmingsubset-sum