A Psychology Experiment It turns out that Alpha Beta Gamma has a psychology division. Currently, they are performing experiments on groups of students. A group of students is feasible if there are no friendships (within the group). Each student has a value, which is an integer from 1 to 10. The total value of an experiment is the sum of the values of all of the students in the experiment. The psychologists go to a school to choose students for the experiment. They have in mind some target for the value of the experiment. If the value does not meet the target, the experiment is not worth doing. The psychologists interview and test the students to determine each student’s value and collect data on their friendships. The psychologists have to do some fine tuning. They consider a group of students and check if that particular group has a feasible subset with total value at least the target. At this point they do not care which students are in the subset or if there is some feasible subset with total value larger than the target. Armed with this information they consider another group of students (which may overlap) to see if that group has a feasible subset that meets the target. They continue doing this until they have found a desirable group. The psychologists then determine a feasible subset of children in that group that has largest total value. There are two computational problems the psychologists must solve: (1) Given a set of students with their values and friendships, and a target T, determine if there is some feasible subset of the students with total value at least T. This is a YES/NO question.
(2) Given a set of students with their values and friendships, find a feasible subset of students with largest total value.
These two problems seem to be hard to solve efficiently. As usual your manager calls you in and asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For each problem, you find an efficient program on the Internet that solves that problem. Unfortunately your budget will only allow you to buy one program.