Вывод подмножества NP-полный?

Рассмотрим следующую задачу:

Имеются N монет с номерами от 1 до N.

Вы их не видите, но вам дано M фактов о них в виде:

struct Fact
{
    set<int> positions
    int num_heads
}

позицийопределяет подмножество монет, а num_heads— количество монет в этом подмножестве, которые являются решками.

Учитывая эти M фактов, вам нужно вычислить максимально возможное количество орлов.

Является ли эта задача NP-полной? Если да, то какая скидка? Если нет, то что такое решение за полиномиальное время?

Например:

N = 5
M = 3
fact1 = { {1, 2}, 1 } // Either coin 1 or coin 2 is a head
fact2 = { {4}, 0 } // Coin 4 is a tail
fact3 = { {2, 4, 5}, 2 } // Out of coins 2, 4 and 5, two are heads

Конфигурация с наибольшим количеством орлов, которая соответствует фактам:

T H H T H

Таким образом, ответ — 3 орла.