Pul məbləğləri#11504

Pul məbləğləri (Həll təhlili)

Sikkələrin bir alt çoxluğunu seçməklə hansı cəmlərin əldə edilə biləcəyini müəyyən etməliyik. Hər bir sikkə:

istifadə edilməyə bilər;
yalnız bir dəfə istifadə edilə bilər.

Buna görə də bu $0/1$ Knapsack məsələsinin bir növüdür.

Bütün sikkələrin cəmi $S = x_{1} + x_{2} + ... + x_{n}$ S = x_1 + x_2 + ... + x_n olsun. $n \leq 100$ n \le 100 və $x_{i} \leq 1000$ x_i \le 1000 olduğundan, $S \leq 100000$ S \le 100000. Bu, hər bir mümkün cəm haqqında məlumatı saxlamağa imkan verir.

Aşağıdakı kimi təyin edək:

d p [s] = {1, 0, əgər s cəmi əldə edilə bilirsə, əks halda .

dp[s] = \begin{cases} 1, & \text{əgər } s \text{ cəmi əldə edilə bilirsə},\\ 0, & \text{əks halda}. \end{cases}

Başlanğıcda biz hələ heç bir sikkə istifadə etməmişik. $0$ cəmi həmişə əldə edilə bilər: $d p [0] = 1$ dp[0] = 1. Bütün digər dəyərlər sıfırdır. Sürətləndirmək üçün $d p$ -ni bitset şəklində saxlayacağıq.

Nominalı $x_{i}$ x_i olan hər bir sikkə üçün:

bitseti $x_{i}$ x_i mövqe sürüşdürürük;
nəticəni ilkin bitsetlə birləşdiririk:

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

dp = dp | (dp << x_i)

$d p [0]$ -dan başqa qurulmuş bitlərin sayını hesablayırıq.

$1$ -dən $S$ -ə qədər olan cəmləri ardıcıl olaraq gəzib $d p [s] = 1$ dp[s] = 1 olanları çap edirik.

Alqoritmin realizasiyası

$ma s k$ bitsetində $d p$ massivini saxlayacağıq.

#define MAX 100010
bitset<MAX> mask;

Sikkələrin sayı $n$ -i oxuyuruq. $d p [0] = 1$ dp[0] = 1 təyin edirik, çünki heç bir sikkə istifadə etmədən $0$ cəmi əldə edilə bilər.

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

$s$ dəyişənində bütün sikkələrin nominallarının cəmini hesablayırıq.

s = 0;

Dövrdə bütün sikkələri ardıcıl olaraq emal edirik.

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

Nominalı $w$ olan sikkəni emal edirik.

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

Qurulmuş bitlərin sayını qaytarırıq. Lakin $0$ cəmi həmişə əldə edilə bildiyindən, onu istisna etmək lazımdır.

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

Bütün əldə edilə bilən müsbət cəmləri çap edirik.

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