gpt4 book ai didi

algorithm - 确定一组数字是否符合要求列表

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

假设您有一组不同的数字 {5,6,1,67,13,9,14,15},以及如下要求列表:R1:你必须从 set(5,6,10) 中选择至少 2 个数字,它们也在你的数组中,在这种情况下它将是 5,6

R2:您必须从集合 (9,13,67,5) 中选择至少 3 个数字,这些数字也在您的数组中。在这种情况下,它将是 9,13,67。请注意,我们不能选择 5,因为它已在 R1 中使用

R3:您必须从集合 (1,14,15,6) 中选择至少 2 个数字,这些数字也在您的数组中。在这种情况下,它可以是 1,14 或 1,15 或 14,15 我们将有多重满足。.....

.....

Rk:你必须从集合 (......) 中选择至少 k 个数字,这些数字也在你的数组中。

所以问题是找到一个多项式时间算法来判断给定的数组是否满足所有要求,并且数组的每个数字只能用于满足一个要求。

我的解决方案是这样的:

determine(array a,R[]) //R[] is a array of requirements, array a is our checking array
{
if R is empty return true //we satisfied all the requirments
if R[0] cannot be satisfied by our array a return false
for each satisfactions
{
new array b=a-selected numbers for this satisfaction
new rule array newR=R-R[0] //remove the first rule of the rule array
if determine(b,newR) is false //we begin our recursive call
we continue our loop since this means the current way of satisfaction does not work
else return true
}
return false //this means we finish checking all the satisfactions and cannot find a match we need to tell the last recursive call that this way does not work
}

显然我的解决方案需要指数时间,任何人都可以提出多项式解决方案吗?

最佳答案

在满足所有要求后,您将选择数组中的每个元素 (c(0), c(1), c(2), ... , c(n)) 次。

其中 c(i) 是 0 或 1。例如,您的约束告诉您 c(i) + c(j) + c(k) = 2。

我可能错了,但这似乎是 0-1 整数规划,这是卡普的 NP 完全问题之一,不是吗?

http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

关于algorithm - 确定一组数字是否符合要求列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13078295/

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