Грошові суми#11504

Грошові суми (Розбір)

Нам потрібно визначити, які суми можна отримати, вибравши деяку підмножину монет. Кожну монету можна:

не використовувати;
використати лише один раз.

Тому це різновид задачі $0/1$ Knapsack.

Нехай сума всіх монет дорівнює $S = x_{1} + x_{2} + ... + x_{n}$ S = x_1 + x_2 + ... + x_n. Оскільки $n \leq 100$ n \le 100 та $x_{i} \leq 1000$ x_i \le 1000, то $S \leq 100000$ S \le 100000. Це дозволяє зберігати інформацію про кожну можливу суму.

Визначимо

d p [s] = {1, 0, якщо суму s можна отримати, інакше .

dp[s] = \begin{cases} 1, & \text{якщо суму } s \text{ можна отримати},\\ 0, & \text{інакше}. \end{cases}

Спочатку ми ще не використали жодної монети. Сума $0$ завжди досяжна: $d p [0] = 1$ dp[0] = 1. Усі інші значення дорівнюють нулю. Для прискорення зберігати $d p$ будемо в бітсеті.

Для кожної монети з номіналом $x_{i}$ x_i:

зсуваємо бітсет на $x_{i}$ x_i позицій;
об'єднуємо результат із вихідним бітсетом:

d p = d p ∣ (d p << x_{i})

dp = dp | (dp << x_i)

Підраховуємо кількість встановлених бітів, крім $d p [0]$ .

Послідовно перебираємо суми від $1$ до $S$ і виводимо ті, для яких $d p [s] = 1$ dp[s] = 1.

Реалізація алгоритму

У бітсеті $ma s k$ будемо зберігати масив $d p$ .

#define MAX 100010
bitset<MAX> mask;

Читаємо кількість монет $n$ . Встановлюємо $d p [0] = 1$ dp[0] = 1, оскільки суму $0$ можна отримати, не використовуючи жодної монети.

scanf("%d", &n);
mask.set(0);

У змінній $s$ обчислюємо суму номіналів усіх монет.

s = 0;

У циклі послідовно обробляємо всі монети.

for (i = 0; i < n; i++)
{

Обробляємо монету з номіналом $w$ .

  scanf("%d", &w);
  s += w;
  mask |= (mask << w);
}

Повертаємо кількість встановлених бітів. Однак сума $0$ завжди досяжна, тому її необхідно виключити.

printf("%d\n", mask.count() - 1);

Виводимо всі досяжні додатні суми.

for (i = 1; i <= s; i++)
  if (mask[i]) printf("%d ", i);
printf("\n");