gpt4 book ai didi

algorithm - Knapsack 的变体是 NP-Complete 吗?

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

在背包问题中,唯一的限制条件是所拾取元素的总大小不大于包裹的总大小。我们知道背包问题是 NP 完全问题。

但是,如果我们有另一个选择固定数量项目的约束,这个问题仍然是 NP-Complete 吗?问题形式化描述如下,

最大化$\sum_{j=1}^n p_j x_j$

s.t. $\sum_{j=1}^n w_j x_j < W$

      $\sum_{j=1}^n x_j = N$

$x_j = \{0,1\}$

这是我研究中的公式化问题,我不确定它是否是 NP-Complete。请帮我。谢谢!

最佳答案

您可以通过从您的 n 对象集中遍历所有大小 N 的组合来解决约束问题。组合数不超过n^N:

C = n! / (N! (n-N)!)
<= n! / (n-N)! // since N! >= 1
= n * (n-1) * ... * (n-N+1) // N terms
<= n * n * ... * n // N terms
= n^N

由于 N 是固定的,因此整体复杂度是多项式的。

关于algorithm - Knapsack 的变体是 NP-Complete 吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16121703/

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