# Tag Info

## New answers tagged matching

2

Your first problem is $\mathsf{NP}$-Complete. Membership to $\mathsf{NP}$ is trivial. To see that it is $\mathsf{NP}$-hard, you can reduce it from Subset Sum. Let $\langle S_1, W_1 \rangle$ be an instance of Subset Sum. Define $S_2$ as the multiset obtained by multiplying each number in $S_1$ by $100$, and $W_2 = 100 W_1$. The instance for your problem is \$\...

Top 50 recent answers are included