带有需要考虑约束的物品的背包
我有项目 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有了这个约束，问题就变成了强 NP 难问题（与离散背包相反，离散背包只是弱 NP 难问题）。假设您所有物品的重量为 1，价值为 1。
决定是否可以实现价值 k（假设背包容量 >= k）相当于查找 k< /em> 之间没有约束的项目。这是一个已知的 NP 难题：独立集。
如果您对约束的性质有一些额外的了解，这可能会更容易。
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.
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.