Money Sums#11504

Money Sums (Анализ)

Written by @Yusif_M and @Tuncay_Pashayev.

You have $n$ coins and you should make different values with using these coins. In the next line you input n intengers - the value of your coins. For this problem we can use knapsack.

We use array for input the value of our coins. Let's call them $a_{0}$ a_0, $a_{1}$ a_1, $a_{2}$ a_2, ..., $a_{n - 1}$ a_{n-1}. Then create another array called $k na p s a c k$ knapsack. The elements will be $k na p s a c k_{0}$ knapsack_0, $k na p s a c k_{1}$ knapsack_1, $k na p s a c k_{2}$ knapsack_2, ..., $k na p s a c k_{k - 1}$ knapsack_{k-1}. In this case the intenger k is the maximum value that we can make with using our coins.

Let's explain knapsack. The maximum value that we can get is the sum of our coin's values:

$k$ = $a_{0} + a_{1} + a_{2} + ... + a_{n - 1}$ a_0 + a_1 + a_2 + ... + a_{n-1}

Our first element of array is $a_{0}$ a_0, if we can make value with using $a_{0}$ a_0, that means we can make another value with using $a_{1}$ a_1 and new value will be $a_{0}$ a_0 + $a_{1}$ a_1. If we can make value with using $a_{0}$ a_0 and $a_{1}$ a_1, that means we can make another value with using $a_{2}$ a_2. The new values will be:

$a_{0} + a_{1} + a_{2}$ a_0 + a_1 + a_2
$a_{0} + a_{2}$ a_0 + a_2
$a_{1} + a_{2}$ a_1 + a_2

It is going like that till we reach the maximum value - k. In the code we write like this:

Implementation

#define MAX 100001 
int knapsack[MAX];

Creating an array called $k na p s a c k$ knapsack. The reason of defining MAX - $100001$ is, the maximum value of $a_{i}$ a_i can get is $1000$ and the maximum value n can get is $100$ . The product makes $100000$ , indexing is starting from $0$ , so we add $1$ more, it makes $100001$ elements for knapsack array.

int n,k = 0;
cin >> n; 
int a[n];

We create intenger - n and intenger - k, making $k = 0$ and creating another array.

for (int i = 0; i < n; i++)
{
    cin >> a[i]; 
    k += a[i]; 
}

Input array elements and finding maximum value with summing the value of our coins.

knapsack[0] = 1;
for (int i = 0; i < n; i++)
{
    for (int j = k; j >= a[i]; j--)
    {
        if (knapsack[j - a[i]] == 1)
            knapsack[j] = 1;
    }
}

C++

First we need to give value $1$ to $k na p s a c k_{0}$ knapsack_0 otherwise all the elements of array - $k na p s a c k$ knapsack will be $0$ , so the answer will be wrong. Then we are checking if we were able to create a value using $a_{i}$ a_i, then we can create a new value with adding $a_{i}$ a_i to $j - a_{i}$ j-a_i to this will give us $j$ , so $k na p s a c k_{j}$ knapsack_j will be $1$ also.

int res = 0;
for (int i = 1; i <= k; i++)
{
    if (knapsack[i] == 1)
        res++;
}
cout << res << endl;

C++

New intenger called res and giving value $0$ . If we were able to create value $i$ increase the value of $r es$ by one. $r es$ is number of different values that we were able to create.

for (int i = 1; i < k; i++)
{
    if (knapsack[i] == 1)
        cout << i << ' ';
}

Then output all the values that we were able to create.

Full Solution

#include <iostream>
using namespace std;

#define MAX 100001
int knapsack[MAX];

int main()
{
    int n,k = 0;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        k += a[i];
    }
    knapsack[0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = k; j >= a[i]; j--)
        {
            if (knapsack[j - a[i]] == 1)
                knapsack[j] = 1;
        }
    }
    int res = 0;
    for (int i = 1; i <= k; i++)
    {
        if (knapsack[i] == 1)
            res++;
    }
    cout << res << endl;
    for (int i = 1; i <= k; i++)
    {
        if (knapsack[i] == 1)
            cout << i << ' ';
    }
}

C++

Written by medv.

We need to determine which sums can be obtained by choosing some subset of the coins. Each coin can be:

not used;
used exactly once.

Therefore, this is a variant of the $0/1$ Knapsack problem.

Let the sum of all coins be $S = x_{1} + x_{2} + ... + x_{n}$ S = x_1 + x_2 + ... + x_n. Since $n \leq 100$ n \le 100 and $x_{i} \leq 1000$ x_i \le 1000, we have $S \leq 100000$ S \le 100000. This allows us to store information about every possible sum.

Define

d p [s] = {1, 0, if the sum s can be obtained, otherwise .

dp[s] = \begin{cases} 1, & \text{if the sum } s \text{ can be obtained},\\ 0, & \text{otherwise}. \end{cases}

Initially, we have not used any coins. The sum $0$ is always achievable, so $d p [0] = 1$ dp[0] = 1. All other values are equal to zero. To speed up the solution, we'll store $d p$ in a bitset.

For each coin with denomination $x_{i}$ x_i:

shift the bitset by $x_{i}$ x_i positions;
combine the result with the original bitset:

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

dp = dp | (dp << x_i)

Count the number of set bits, excluding $d p [0]$ .

Then, iterate through all sums from $1$ to $S$ and print those for which $d p [s] = 1$ dp[s] = 1.

Algorithm implementation

In the bitset $ma s k$ , we'll store the $d p$ array.

#define MAX 100010
bitset<MAX> mask;

Read the number of coins $n$ . Set $d p [0] = 1$ dp[0] = 1, since the sum $0$ can be obtained by using no coins.

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

In the variable $s$ , we calculate the sum of the denominations of all coins.

s = 0;

Process all coins one by one in a loop.

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

Process the coin with denomination $w$ .

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

Return the number of set bits. However, the sum $0$ is always achievable, so it must be excluded.

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

Print all achievable positive sums.

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