UVa 11856 - Ferry Loading V

// UVa 11856 - Ferry Loading V

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
using namespace std;

int gen[1000001], R[1000001];
bool T[1000001];

int main() {
	int n;
	while (scanf("%d", &n) && n) {
		double r[100], W = 0;
		for (int i = 0; i < n; i++) {
			scanf("%lf", &r[i]);
			W += r[i];
		}
		int a[100];
		for (int i = 0; i < n; i++)
			a[i] = round(r[i] * 10000 / W);

		memset(T, false, sizeof(T));
		T[0] = true;
		gen[0] = 0;
		int m = 1;
		for (int i = 0; i < n; i++) {
			for (int j = m - 1; j >= 0; j--) {
				if (!T[gen[j] + a[i]]) {
					T[gen[j] + a[i]] = true;
					R[gen[j] + a[i]] = i;
					gen[m++] = gen[j] + a[i];
				}
			}
		}

		for (m = 5000; m >= 0 && !T[m]; m--)
			;
		vector<int> sol;
		while (m != 0) {
			sol.push_back(R[m]);
			m -= a[R[m]];
		}
		for (int i = sol.size() - 1; i > 0 ; i--)
			printf("%d ", sol[i]+1);
		if (sol.size() > 0)
			printf("%d\n", sol[0]+1);

	}
	return 0;
}