小编use*_*882的帖子

我理解为什么有界度生成树被认为是NP完全的度数或2(它是哈密顿路径问题的一个实例),但我不明白为什么这适用于度> 2.如果有人可以请解释为什么这是对于程度> 2的NP完全问题,这将是最有帮助的

我刚在想,

我想对背包问题做一个变化.

想象一下原始问题,具有各种权重/值的项目.

我的版本将与正常权重/值一起包含"组"值.

例如.Item1 [5kg,$ 600,电子] Item2 [1kg,$ 50,食物]

现在,有了这样的一组项目,我将如何编码背包问题以确保选择每个"组"中最多1个项目.

笔记:

1. 您无需从该组中选择项目
2. 每组中有多个项目
3. 你仍然在减轻体重,最大化价值
4. 组的数量是预定义的,以及它们的值.

我只是在这个阶段编写代码草案,我选择使用动态方法.我理解常规背包问题的动态解决方案背后的想法,我如何改变这个解决方案以包含这些"组"？

KnapSackVariation(v,w,g,n,W)
{
  for (w = 0 to W)
     V[0,w] = 0;
  for(i = 1 to n)
     for(w = 0 to W)
        if(w[i] <= w)
           V[i,w] = max{V[i-1, w], v[i] + V[i-1, w-w[i]]};
        else
           V[i,w] = V[i-1, w];
     return V[n,W];
}

这就是我到目前为止所需要的,需要添加它以便它会在每次解决这个问题时从组中删除所有相应的项目.

我试图通过检查值的总和<100来向表中添加约束。

这是我的架构：

  CREATE TABLE Works  (
     eid      INTEGER,
     did      INTEGER,
     pct_time INTEGER,
     PRIMARY KEY (eid,did),
     FOREIGN KEY (eid) REFERENCES Employee(eid),
     FOREIGN KEY (did) REFERENCES Dept(did)
  );

我需要检查每个eid的pct_time的总和是否<= 100。

例如

eid --- did ---- pct_time
0 ----- a ------- 50
0 ----- d ------- 40
0 ----- c ------- 20
1 ----- a ------- 90
1 ----- b ------- 10
2 ----- d ------- 40
2 ----- a ------- 20

在这里，当我将eid 0的第三个条目添加为sum> 100时，它应该出错。
对于eid 1和2，因为pct_time <= 100
会很好。这怎么办？

到目前为止，我所做的只是

ALTER TABLE …