[287] NP-Complete

Title Text:General solutions get you a 50% tip. Origin:https://xkcd.com/287/ https://www.explainxkcd.com/wiki/index.php/287:_NP-Complete https://app-xkcd-cn.appspot.com/ “我的爱好”系列漫画中的另一个条目。 Cueball在餐馆订单中嵌入NP完全问题。具体来说,他不是通过明确说明名称,而是通过它们的总价格来订购开胃菜。这是背包问题的简化示例。这是组合优化中的一个问题,如下所示:如果你有一个可以容纳特定重量的背包(背包或帆布背包),并且你有一组物品,每个物品都有自己的指定值和重量,你必须选择放入背包的物品,使重量不超过背包的容量,并使所有物品的组合值… Read more

Categories: