0-1背包有其他限制（彩色物品）？ [英] 0-1 Knapsack with additional restriction (colored items)?

问题描述

我主要是出于在工作中的停机时间而解决这个问题的。

I'm working on this problem mostly out of curiosity in my downtime at work.

想象一下正常的0-1背包问题，除了所有物品都是黄色，红色，蓝色或绿色，并且由于您的强迫症，您的背包中必须正好有2种每种颜色的物品。因此，除了正常项目外，每个项目还具有3个属性：重量，值，颜色。

Imagine the normal 0-1 Knapsack problem, except all the items are either yellow, red, blue, or green, and due to your OCD you must have exactly 2 items of each color in your knapsack. So instead of the normal items each item has 3 properties: Weight, Value, Color.

这还是背包问题，还是最好用其他方式定义？

Is this even still a knapsack problem, or is it better define in some other way?

推荐答案

我将使用 nCk 表示 n选择k为了便于键入。由于每种颜色必须精确地包含2个项目，因此可行解的数量为O（ nC2 ），也就是O（ n ^ 2 ）。每个解都可以在多项式时间内求值，因此该问题在多项式时间内也可以解决。换句话说，它比常规的背包问题要简单得多。

I'll use nCk to represent "n choose k" for ease of typing. Since you must have exactly 2 items of each color, the number of feasible solutions is O(nC2), which is O(n^2). Each solution can be evaluated in polynomial time, so the problem is solvable in polynomial time as well. In other words, it's far simpler than a regular knapsack problem.

这篇关于0-1背包有其他限制（彩色物品）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！