Problem

[3UNKNOWN3]

Okay, so I was at a programming competition today and my team was programming in QBasic (I know.). Anyway, we went through the first 4 problems (there were 5 in all) much faster than everyone else, but the last one just stumped us and we lost. I've done some more coding today, using C++ and FreeBasic and I couldn't get a working solution. I would like help with the solution in C++ (C is fine too). The problem read as follows:
The stores in a mall are offering free coupons. Each store's coupon has a specific dollar value. The dollar values are different for different stores. Customers are free to pick up one coupon from each store except that no one is allowed to pick up coupons from two adjacent stores. Assume there are 10 stores arranged in a single row and that you want to pick up coupons with as large a total dollar value as possible.
Write a program which inputs 10 positive integers corresponding to the coupon dollar value in the same order as the stores in the mall, and the outputs the chosen dollar values needed to get the maximal total, together with the total.

For example,
If the input is: 5 7 3 1 4
The output should be: 5 3 4 12

If the input is: 8 1 2 6 3
The output should be: 8 6 14

Thanks for any help. I REALLY want to know how you would go about doing this.

[teknomage1]

Well, you've got two sub problems here. The first is to generate permutations of the input list with certain restrictions. The second is to find a maximal value for the sum of a valid permutation.

One way to do it in C/C++ would be to represent each solution to the problem as a binary number with ones indicating the coupons a user took. So if I took the coupons from stores 1,3,5,7,9 the solution would look like '1010101010' . You can then write a function to convert a bit vector like this to sum using the input numbers.

Now that yoou have a representation for the solutions, you'll need an array to store them in. You could safely make this array global and have a function which adds solutions to the array, and another function that calulates the maximum value by iterating over this array, converting the bitvectors to integers representing the total value of the coupons they represent.

So that just leaves finding the permutations. Since the problem says you can't get coupons from any adajacent store you can write a recursive function that takes an index value and a partial solution, that iterates over all legal stores further down the line from itelf, and calls itself on those stores. (I know that was confusing so maybe a bit of code would explain it more clearly)

/* hop from store to store */
void find_next_valid_store(int index, int solution_vector) {
     for (int i=index+1;i<10;i++) {
          /*find the next non-adjacent store from index */
	  int valid_store =  i + 1; 
          /*add this storeplus any previous stores to our list as a possible solution */
	  int new_solution = update_bitvector(solution_vector, valid_store);  
	  add_solution( new_solution);
	  find_next_valid_store(valid_store, new_solution);
     }
}
/* all valid solutions could be found by starting at each store and then running find_next_valid */
for(int i=0; i < 10; i++) {
         find_next_valid_store( i, make_bitvector_starting_at( i ) );
}