gpt4 book ai didi

arrays - 部分和查找/部分和集分配

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:04:44 26 4
gpt4 key购买 nike

我有以下问题需要解决。作为输入,我有 2 个十进制数组。两者的元素之和相等。实际问题是通过部分和将一个数组的值分配给第二个数组 - 如果一个数组中的某些元素是第二个数组中任意数量元素的总和 - 它们应该相互分配。

示例 1:

数组 1:25.0、25.0、50.0、50.0Array2: 50.0, 100.0

预期结果:50.0是25.0和25.0之和,100.0是50.0和50.0之和
(0->0,1; 1->2,3)

示例 2:

数组 1:20.0、70.0、80.0、130.0Array2: 100.0, 200.0

预期结果:100 = 20+80, 200 = 70+130 (0->0,2; 1->1,3)

想法是返回分配的数组元素索引并返回尽可能少的分配。

最佳答案

这叫做 subset sum problem .

不幸的是,这是 NP 完全的,这意味着您必须检查所有可能的组合。

但是,如果您的问题只有少量的部分和(例如您的示例),则可以用蛮力解决。


白痴是对的,并不是所有的 NP 完全问题都需要检查所有可能的组合。
不过我相信subset sum is one that does .

关于arrays - 部分和查找/部分和集分配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5037991/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com