解决背包的变体，其中物品的价值取决于背包中已有的物品
Solving a variation of the knapsack in which the value of an item depends on items that are already in the sack
我正在尝试解决以下问题：
我有一组 N 个项目，其中每对项目都有一个相互分数，我需要 select 一个 W 个项目的组合，以使总分最高。
例如 i,j,k 项的总分是
score(i,j) + score(i,k) + score(j,k).
为了避免遍历所有 N^W 可能的组合，我考虑对 0-1 背包问题做一个变体，并通过以下 2 个更改使用动态编程来解决：
- 将所有权重设置为 1（这样最终我的袋子里就会得到
W 件物品）
- 我将根据当前正在检查的项目和此时已经在麻袋中的项目来计算值 "on the fly"，而不是每个项目都有一个常量值数组。
我已经开始编写具有这两个更改的解决方案，但是现在我想得更多，我担心它不能用动态编程来解决，因为 "optimal substructure" 属性不成立。
例如，如果W=3和项目i,j,k是最优解，那么对于W=2，i,j不一定是最优解（根据上面总分的计算） .
有没有人知道如何使用动态编程而不是 O(N^W) 蛮力解决这个问题？
谢谢
您的问题是 NP-hard 问题，这意味着几乎可以肯定没有快速的多项式时间算法可以解决它，因为没有人能够想出多项式时间算法来解决 NP-hard 问题。要查看 NP 硬度，假设您有一个图形，其中节点是您的索引，并且如果 i 和 j 之间存在边，则将 i，j 之间的分数定义为 1，否则为 0。然后如果可以，在多项式时间内，找到最多包含 W 个节点的节点的最大分数子集，然后您可以在多项式时间内计算出图中是否存在大小为 W 的团。这是一个NP完全问题。
我正在尝试解决以下问题：
我有一组 N 个项目，其中每对项目都有一个相互分数，我需要 select 一个 W 个项目的组合，以使总分最高。
例如 i,j,k 项的总分是
score(i,j) + score(i,k) + score(j,k).
为了避免遍历所有 N^W 可能的组合，我考虑对 0-1 背包问题做一个变体，并通过以下 2 个更改使用动态编程来解决：
- 将所有权重设置为 1（这样最终我的袋子里就会得到
W件物品） - 我将根据当前正在检查的项目和此时已经在麻袋中的项目来计算值 "on the fly"，而不是每个项目都有一个常量值数组。
我已经开始编写具有这两个更改的解决方案，但是现在我想得更多，我担心它不能用动态编程来解决，因为 "optimal substructure" 属性不成立。
例如，如果W=3和项目i,j,k是最优解，那么对于W=2，i,j不一定是最优解（根据上面总分的计算） .
有没有人知道如何使用动态编程而不是 O(N^W) 蛮力解决这个问题？
谢谢
您的问题是 NP-hard 问题，这意味着几乎可以肯定没有快速的多项式时间算法可以解决它，因为没有人能够想出多项式时间算法来解决 NP-hard 问题。要查看 NP 硬度，假设您有一个图形，其中节点是您的索引，并且如果 i 和 j 之间存在边，则将 i，j 之间的分数定义为 1，否则为 0。然后如果可以，在多项式时间内，找到最多包含 W 个节点的节点的最大分数子集，然后您可以在多项式时间内计算出图中是否存在大小为 W 的团。这是一个NP完全问题。