给定一组具有值的项目,确定要包括在集合中的每个项目的数量,使得总值小于或等于给定限制,并且总值尽可能大.
例:
Product A = 4 Product B = 3 Product C = 2 Product D = 5 If Total Capacity = 10.5 , then the combination of B,C,D will be selected. If Total Capacity = 12.5 , then the combination of A,B,D will be selected. If Total Capacity = 17 , then the combination of A,B,C,D will be selected.
我正在寻找一种算法(如背包或垃圾箱包装)来确定组合.任何帮助赞赏.
通常提出的旅行推销员问题是找到连接所有城市的最便宜的路线.这不是决策问题,我们无法直接验证任何建议的解决方案.我们可以将其重申为一个决策问题:给定成本C,是否有比C便宜的路线？这个问题是NP完全的,通过一些工作,我们可以像修改的NP完全形式一样轻松地解决原始TSP.因此,TSP是NP难的,因为它至少与NP完全问题一样难.
我知道TSP是NP-Complete但问题是NP-Hard？我读到NP中但不是P中的问题是NP-Hard.我无法将此事与TSP联系起来.请解释一下.
我正在寻找NP和NP完全问题之间的区别.我在Jason的StackOverflow中找到了这个很棒的答案.关于NP完全问题,他说
NP问题X,在多项式时间内可以减少任何其他NP问题Y到X. 直观地说,这意味着如果我们知道如何快速解决X,我们可以快速解决Y. 确切地说,如果存在多项式时间算法f,则Y可简化为X,以便在多项式时间内将X的实例x转换为Y的实例y = f(x),并且当且仅当答案时,x的答案为是到f(x)是肯定的.
我的问题是:哪一个是NP完全问题,X还是Y？
我知道您不能提供验证证书。但是，我只是在想，为什么我们不能将输入提供给 NDTM 决定 SAT，然后反转答案？漏洞在哪里？
假设我们有两个长度相同的列表，ls1和ls2。例如，我们有
ls1 = [4, 6]
ls2 = [3, 5]
并为每个元件中ls1，我们有与一个元件与一个元素配对它ls2，以这样的方式，使得总（绝对在元件之间）的差异ls1，并在元件ls2是最小的。一个元素只能匹配一次。在上面的例子中，最佳的方式是匹配4是ls1用3在ls2，并5在ls1与6中ls2，其产生的总差
(4 - 3) + (6 - 5) = 2
我需要一个程序来返回这两个列表中的元素之间的最小总差。列表的长度是任意的，列表中元素的值也是任意的（但它们都是正整数）。
我目前知道，使用置换暴力破解解决方案是一个选择，但是我需要的是具有最佳时间和空间复杂度的代码。我听说过动态编程的概念，但是我不知道该如何实现它。预先感谢您的答复。
附言 这是我当前使用置换的蛮力代码，在运行时或内存使用方面效率不高：
from itertools import permutations
def minimum_total_difference(ls1, ls2):
length = len(ls1)
possibilities = list(permuations(ls1, length))
out = 10**10
for possibility in possibilities:
out_ = 0
for _ in …如果算法的输入大小为2 ^ n,则算法以$ O(n2 ^ n)$ time运行.在这种情况下,我们可以说算法在输入大小的多项式时间内运行吗？
通过尝试所有可能性，计算给定字符串的所有字符串排列可以在 O(n!) 中解决。
现在，看看旅行商问题，我们可以通过尝试城市的所有排列来解决它。假设我们有城市 A、B 和 C。假设我们从城市 A 开始。通过计算 BC 字符串的所有排列，我们得到 ABC ACB，然后我们只需求和（在多项式时间内，AB、CB 和 CA 之间的距离为第一个案件...）
那么这不是旅行商问题的所有字符串排列的减少吗？它不是一个NP完全问题吗？
假设您要创建一个哈希表,将每个可能的有效9x9数独(尚未填写)映射到其解决方案.(这是不可行的任务)
然后你要创建一个简单的程序,它将一个有效的9x9数据(再次,尚未填充)作为输入,并返回在上述哈希表中映射到它的解决方案.
这不会被认为是在多项式时间内工作的数独求解器吗？
有没有关于这个理论解决方案的东西使它无法证明数独是P类问题？
我正在研究P，NP和NP-Complete问题，并且遇到了一些问题。
我知道，如果可以在多项式时间内求解，则问题为P，如果可以在多项式时间内验证，则问题为NP。我也理解，如果问题是NP，则它是NP-Complete，并且可以从现有的NP-Complete问题中减少。
我知道SAT，3-SAT，独立集，顶点覆盖，哈密顿周期，子集总和和旅行商都是NPC。但是我遇到一个问题，我被告知判断图形中是否存在5个顶点的独立集合实际上是多项式时间可解的，而不是NPC。然后，这使我感到困惑，因为我认为独立集合问题是NPC。
因此，这使我想知道，在什么情况下这些“ NPC”问题不是NPC，实际上是P？遇到问题时，如何确定问题是P还是NPC？如果该问题确实有可解决的时间问题，该怎么办，我只是无法解决该问题，因此沿NPC走了。我怎么知道我做错了？