问在2个可能的数组元素数之间选择，以获取和“%s”
EN

Stack Overflow用户

提问于 2020-05-20 17:32:24

回答 1查看 34关注 0票数 0

我有一些算法问题，我有三个数组X，Y和A大小为n，我有X和Y的值，但是A是空的，我想填充它，所以Ai要么是Xi，要么是Yi，我想看看A中元素的和是否可以是某个值S，如果是，如何呢？

我认为这个问题可以通过动态编程来解决，但我不知道如何解决

另外，我不想要时间复杂度超过O(n *n* log(n))的算法。

发布于 2020-05-20 18:13:19

你不能解决这个问题，因为一开始

C = [min(x[0], y[0]), min(x[1], y[1]), min(x[2], y[2]),...]

在那之后你就有了B = [abs(x[0] - y[0]), abs(x[1], y[1]), abs(x[2], y[2]), ...]

你应该有T = (s - (SUM(C)))

并从B中选择sum数字等于T，您无法解决它:|

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/61909690

复制

相似问题

问在2个可能的数组元素数之间选择，以获取和“%s”EN