int n, a[n]; // вещи
int W; // максимальный вес

int last[W + 1]; // для каждого веса номер последней вещи

void solve() {
  fill(last, last + W + 1, -1); // не достижимо
  last[0] = 0;
  for (int i = 0; i < n; i++) // добавляем вещь i
    for (int x = W - a[i]; x >= 0; x--)
      if (last[x] != -1 && last[x + a[i]] == -1)
        last[x + a[i]] = i;
}