带物品的背包要考虑约束 [英] Knapsack with items to consider constraint

问题描述

我有I1，I2，I3，I4项，权重为W1 ... W4，值为V1 ... V4。我想以最小的权重最大化值。这是传统的背包。但是，存在一些小的约束，某些项目无法一起使用。因此，可以说I2和I3无法在一起。任何人都可以为它提供动态编程解决方案或任何其他解决方案。

I have items I1, I2, I3, I4 with weights W1...W4 and Values V1...V4. I want to maximize values with minimum weights. This is a traditional Knapsack. However there is small constraint some items cannot go together. So lets say I2 and I3 cannot go together. Can anyone provide a dynamic programming solution or any other solution for the same.

推荐答案

在此约束下，问题变得很严重（与离散背包相对，NP背包相对较弱）硬。假设所有项目的权重均为1，且值为1。

With this constraint, the problem becomes strongly (as opposed to discrete knapsack, which is only weakly NP-hard) NP-hard. Suppose all your items have weight 1 and value 1.

确定是否可以实现值 k （假设背包容量> = k ）等同于找到在它们之间没有约束的 k 个项目。这是一个已知的NP难题：独立集。

Deciding whether you can achieve value k (assuming knapsack capacity >= k) is equivalent to finding k items that have no constraint between them. This is a known NP-hard problem: independent set.

如果您对约束的性质有更多了解，这可能会更容易。

This might be easier if you have some additional knowledge about the nature of the constraints.

这篇关于带物品的背包要考虑约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！