首页 文章

0-1背包有额外限制(彩色物品)?

提问于
浏览
2

我正在解决这个问题主要是出于对工作中停工的好奇心 .

想象一下正常的0-1背包问题,除了所有项目都是黄色,红色,蓝色或绿色,并且由于你的OCD,你的背包中每种颜色必须正好有两项 . 因此,除了正常项目,每个项目都有3个属性:权重,值,颜色 .

这甚至还是背包问题,还是以其他方式更好地定义?

1 回答

  • 1

    为了便于输入,我将使用 nCk 代表"n choose k" . 由于每种颜色必须正好有2个项目,因此可行解决方案的数量为O( nC2 ),即O( n^2 ) . 每个解决方案都可以在多项式时间内进行评估,因此问题也可以在多项式时间内解决 . 换句话说,它比常规的背包问题简单得多 .

相关问题