1/0 带加权边缘的背包变化
1/0 Knapsack Variation with Weighted Edges
我目前正在调查一个路线问题（找到我想去但不超过最长旅行时间的地方的子集[每个都有一定的分数]）并想出了 1/0 背包的变体似乎解决了我原来的问题的问题。
根据维基百科，1/0 背包描述为：
Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
因此对于每个项目都有一个固定的重量（质量），可以在尝试解决问题时轻松使用，例如使用动态规划。
但是如果特定物品的重量取决于袋子之前的内容怎么办？换句话说（并且以更一般的方式）：让我们考虑以下完整图表：
每个节点 (A,B,C,D,E) 代表一个我可能想放入背包的物品。让我们假设每个节点也有一个特定的 value 分配给它（图中遗漏）。我仍然想要一个最佳背包，因此是具有最高分数的节点子集，但是这次权重（或将特定节点添加到我当前背包的成本）没有分配给节点本身，而是分配给边缘导致它。
这意味着添加节点的成本取决于背包的先前内容（例如，使用任何已包含节点中成本最低的边）。例如，如果我当前的背包由 {A,C} 组成，则添加 B 的成本为 2（采用 A->B 或 C->B）。如果我当前的背包由 {D,E} 组成，则添加 B 的成本为 3。
不幸的是，我真的想不出一个好的算法来解决这个问题。
经典的背包 DP 方法在这里并不真正起作用，因为您可以轻松地构建它不是 return 最佳解决方案的情况。例如，如果您开始使用 "wrong" 个节点构建背包，添加一个非常好的节点（应该包含在最佳解决方案中但尝试很晚）的成本可能会超过容量。
我是不是采取了完全错误的方法来解决这个问题？你认为有更好的算法来解决这个问题吗？
首先，这个问题是NP难的。这是从加权完全图中的最短汉密尔顿路径到这个的减少。给定一个图，我们可以将所有节点的值分配给 1，然后对答案进行 运行 二进制搜索。如果此问题有多项式解，它可以判断是否存在包含所有顶点且不长于给定值的路径。因此，我们将能够在多项式时间内解决最短哈密顿路径问题。实际上，这意味着没有人知道您的问题的有效正确多项式解决方案。
现在有两条路可以走：
如果顶点数比较少（20个左右），可以用动态规划求解。状态是(mask, last_vertex)。该值是我们访问 mask 中的所有顶点并在 last_vertex 中停止所需的最短时间。该解的时间复杂度为O(2^n * n^2).
如果顶点数大很多，可以求一个近似解。有很多方法可以做到这一点：启发式、不同的贪心算法、具有局部优化的随机抽样等等。
我目前正在调查一个路线问题（找到我想去但不超过最长旅行时间的地方的子集[每个都有一定的分数]）并想出了 1/0 背包的变体似乎解决了我原来的问题的问题。
根据维基百科，1/0 背包描述为：
Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
因此对于每个项目都有一个固定的重量（质量），可以在尝试解决问题时轻松使用，例如使用动态规划。
但是如果特定物品的重量取决于袋子之前的内容怎么办？换句话说（并且以更一般的方式）：让我们考虑以下完整图表：
每个节点 (A,B,C,D,E) 代表一个我可能想放入背包的物品。让我们假设每个节点也有一个特定的 value 分配给它（图中遗漏）。我仍然想要一个最佳背包，因此是具有最高分数的节点子集，但是这次权重（或将特定节点添加到我当前背包的成本）没有分配给节点本身，而是分配给边缘导致它。
这意味着添加节点的成本取决于背包的先前内容（例如，使用任何已包含节点中成本最低的边）。例如，如果我当前的背包由 {A,C} 组成，则添加 B 的成本为 2（采用 A->B 或 C->B）。如果我当前的背包由 {D,E} 组成，则添加 B 的成本为 3。
不幸的是，我真的想不出一个好的算法来解决这个问题。 经典的背包 DP 方法在这里并不真正起作用，因为您可以轻松地构建它不是 return 最佳解决方案的情况。例如，如果您开始使用 "wrong" 个节点构建背包，添加一个非常好的节点（应该包含在最佳解决方案中但尝试很晚）的成本可能会超过容量。
我是不是采取了完全错误的方法来解决这个问题？你认为有更好的算法来解决这个问题吗？
首先，这个问题是NP难的。这是从加权完全图中的最短汉密尔顿路径到这个的减少。给定一个图，我们可以将所有节点的值分配给 1，然后对答案进行 运行 二进制搜索。如果此问题有多项式解，它可以判断是否存在包含所有顶点且不长于给定值的路径。因此，我们将能够在多项式时间内解决最短哈密顿路径问题。实际上，这意味着没有人知道您的问题的有效正确多项式解决方案。
现在有两条路可以走：
如果顶点数比较少（20个左右），可以用动态规划求解。状态是
(mask, last_vertex)。该值是我们访问mask中的所有顶点并在last_vertex中停止所需的最短时间。该解的时间复杂度为O(2^n * n^2).如果顶点数大很多，可以求一个近似解。有很多方法可以做到这一点：启发式、不同的贪心算法、具有局部优化的随机抽样等等。