Subset Sum Problem

Little Timmy's grandmother gave him 5 black stones and 4 gray stones ‚Äčand told him to find a group of black stones that weigh the same as a group of gray stones. If he can find these groups, he should put them on his window sill to bring calmness into his life. Otherwise, he'll have to fetch more stones. To do this, Timmy decides to ask his mom for a balance to undertake the task. Although he doesn't know this, the set of weights, in pounds, for each stone is the following:

\( B = \{3, 8, 5, 5, 2\} \)

\( G = \{4, 9, 7, 6\} \)

Will Timmy find two groups of stones that weigh the same?

More generally, will this class of problems take polynomial-time, meaning that it is in \(P\), and can also be solved using non-deterministic polynomial-time, meaning that it is also in \(NP\); or can he solve it only using non-deterministic polynomial-time algorithms, meaning that it is only in \(NP\)?

×

Problem Loading...

Note Loading...

Set Loading...