具有相依选择的背包问题
就像经典的背包问题一样，我们希望在不让总重量超过容量的情况下最大化总价值，并且它们的价值和重量是独立的。但是，对于某些项，如果你想选择它，你必须选择其他一些项。
对于ExMaple:item_1、item_2、...、item_n。如果你想选择项目1，你必须选择项目3和项目5，如果你想选择项目3，你必须选择项目2、7和9...等等。
给定一组项，选择总价值最大的子集，但受所选项的总重量不超过固定容量的约束。一组项的总价值是各个值的总和，总权重是各个权重的总和。在集并背包问题中，每个项都有一个值，但每个项都对应一组元素，而不是权重。每个元素都有权重。一组项的总价值是各个项的值之和，但总权重是相应集合并中元素的权重之和。
但它只结合了“权重”，某些物品的价值可能会积累数倍。
有没有什么方法可以有效地解决这个问题？
第2步。将此图转换为组件图（使用DFS查找强连接组件）以消除循环
第三步。因此，现在，这成为一个优先约束背包问题或偏序背包问题。这些问题都是强NP完全的，但是有很多论文都讨论过这一点，并且可以找到一个近似算法来求解。
共有1个答案
在选择项目之前，您必须检查天气项目是否创建循环，如果它创建循环，然后丢弃它，并移动到下一个项目。为此，您可以使用克鲁斯卡尔的算法。
-
问题内容： 我有一张桌子，像这样： 我想选择具有相同基因座和染色体的所有行。例如，第3行和第4行。一次可能有2个以上，并且它们可能不是按顺序排列的。 我尝试了这个： 但是，即使重复，它总是返回第3行，从不返回第4行。我想我缺少明显而简单的东西，但我茫然。 有人可以帮忙吗？ 问题答案： 您需要了解，当您在查询中包含内容时，您是在告诉SQL合并行。您将为每个唯一值获得一行。在随后过滤这些组。通常，您可
-
我是jQuery/js的新手，遇到了这样的问题：您可以运行我的代码，发现计数不正确： null null 我的HTML必须保持不变，我必须找到一些方法使jQuery在本例中工作，并且保持HTML结构不变。如果您对如何解决此问题有任何想法，请随时发表评论或分享代码想法。 我感谢您的帮助！
-
问题内容： 我想在其CSS包含特定背景色的情况下选择一堆。我该如何实现？ 问题答案： 如果我正确理解问题，则选择器 将不起作用， 因为其中不包含“ background- color”属性。您可以快速进行测试以确认它不匹配任何内容： 给出： 这里有一个片段， 将工作 ：
-
问题内容： 该主题的解决方案使我不知所措。 我有一个看起来像的表格（除与我的问题无关的其他字段之外）： 名称，卡号，会员类型 现在，我想要一个显示卡号和成员类型相同的行的视图。这两个字段都是整数。名称为VARCHAR。名称不是唯一的，并且相同的名称也应显示重复的卡号，会员类型。 即，如果下表是表格： 我想要： 只需按卡号排序即可使其对人类有用。 最有效的方法是什么？ 问题答案： 由于您提到的名称可
-
问题内容： 我不知道该如何称呼这个问题。如果你有更好的话请指正我。 我有两个表，用户和帖子。 使用者： 帖子： 现在，我要列出“最活跃”的用户-写得最多的用户。具体来说，我想要结果。 我可以得到预期的结果。但是，如果某些用户拥有相同数量的帖子，则排名可能不会是“ 公平的 ”。 例如，我可能会得到如下结果： 在这里，实际上还有几个拥有帖子的用户。 因此，这可能不是确切的结果。如何获得包含帖子的额外用
-
android L开发人员预览版中的标准列表视图选择器使用颜色控制亮点用于触摸的涟漪效果，并且在不聚焦状态下具有透明背景。 我想定义一个项目，它有一个彩色背景，并且仍然用相同的高亮颜色显示触摸时的涟漪效果。现在，如果我定义以下可绘制图形： 它起作用，但是纹波在 ListVIEW 项中间开始，不管触摸位置如何。如果我在 之外使用相同的背景，例如，对于 ，其工作原理与预期相同（纹波从触摸位置开始）。
-
问题内容： 我的表是： 我想列出一组具有相同疾病的患者。pid和did分别是患者和疾病表中的主键，并且是has_disease表中的外键。 样本数据： 耐心 疾病 has_disease 以上数据的答案是因为它们具有完全相同的疾病1和3，即疟疾和病毒热。我想知道如何在mysql中实现这一点。 。 问题答案： 该查询返回给我们患者及其疾病。 通过完整的剂量列表比较2组患者，并将pid保留为相同的剂量
-
主要内容：动态规划解决01背包问题,01背包问题的具体实现商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品。装哪些商品才能获得最大的收益呢？在限定条件内找到最佳的物品组合，这样的问题统称为背包问题。 根据限定的条件不同，背包问题还可以细分： 部分背包问题：所有物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包； 0-1 背包问题：所有物品不可再分，要么整个装入背包，要么放弃，不允许出现“仅选择物品