This assignment is due by 2:00 p.m. on Tuesday, 2 April.
See the assignment turn-in page (last modified on 22 January 2002) for instructions on
turning in your assignment.
Given an integer pair p, the first integer is called p.first and the
second integer is called p.second.
Given a set s of integer points, the first-sum is the sum of all the
first integers in the set:
first-sum(s) = sum(p.first) for all p in s.
Similarly, the second-sum is the sum of all the second integers in the
set:
second-sum(s) = sum(p.second) for all p in s
Given a set s of integer points, the difference-sum is the absolute
value of the difference between first-sum(s) and second-sum(s);
that is
difference-sum(s) = | first-sum(s) - second-sum(s) |
for the same set s of integer pairs, the total-sum is the sum of the
first and sums:
total-sum(s) = first-sum(s) + second-sum(s)
Write a procedure that accepts a vector of integer pairs V and an
non-negative integer n and returns an n-element subset of the integer
pairs S having the following properties:
- The difference-sum of the returned subset is among the smallest of the
difference-sums of all possible n-element subsets of V. That is, if
s is the returned subset, then
difference-sum(s) <= difference-sum(s) for any n-element
subset s' of V
- If s' is another n-element subset of V having the same
difference sum as s, then the total sum s is no smaller than the
total sum s'. That is,
For any n-element subset s' of V, if
difference-sum(s) == difference-sum(s'), then
total-sum(s') <= total-sum(s).
The prototype for your procedure should be
std::vector<unsigned> pick_pairs(
const std::vector<std::pair<int, int> &, unsigned n);
Your procedure returns not the pairs themselves, but the indices of the input
vector for the pairs in the subset. If n is greater than the input vector
size, your procedure should print an error message and exit.
You can test your procedure by compiling it with the file
/export/home/class/cs-509/pa5/main.cc
and running the resulting executable. This will not be the file I use to test
your code.
This page last modified on 19 March 2002.