pas.andrei's blog

Maximum number of possible different sums
By pas.andrei, 9 years ago, In English

Given an array (multiset) of N elements, find the maximum number of subsets such that the sum of elements in each of the subsets is different and smaller than k.

Example: N = 4 a = {1, 1, 3, 5}

Out of all the 2^4 possible subsets of array a, 11 of them (including empty subset) have distinct sums.

Restricions: 1 <= N <= 1000 1 <= a[i] <= 50000 1 <= k <= 50000 Time limit: 0.4s Memory limit 16 MB

It is tagged as Dynamic Programming problem on the site I took it but I couldn't find any recursive formula in 2 days, so I thought that you can help me.

EDIT: I finally came up with a solution, which I'd rather classify as BFS.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This might be helpful.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you kindly provide the link of the problem? :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I could have provided a link, but the statement is in romanian. Anyway I finally solved this problem.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In order to solve the problem we should first create a vector of integers, let's call it S and an boolean array found, in which found[x] means that for the value x there was already found a subset whisch sums to x.

We take all elements of the array a one by one: a1, a2, ..., an and if one of those number was not found already we insert it in S and mark it as found. Now, let's say we ar at the i-th element in a and that we have m values in S, we now check for each j, 1 <= j <= m, if the value S[j] + a[i] is new, and if it is we mark it as found and insert it in S. In the end, the answer is the amount of values in S + 1 (1 is for the empty subset).

#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("fisier.in");
ofstream fout("fisier.out");

int a[1000];
bool found[50001];
vector<int> S;

int main() {
	int n, k, i, j, m;

	fin >> n >> k;

	for (i = 0; i < n; ++i)
		fin >> a[i];

	found[0] = true;
	for (i = 0; i < n; ++i) {
		if (a[i] <= k) {
			if (found[a[i]] == false) {
				S.push_back(a[i]);
				found[a[i]] = true;

				m = S.size() - 1;
			}
			else
				m = S.size();

			for (j = 0; j < m; ++j) {
				if (a[i] + S[j] <= k && found[a[i] + S[j]] == false) {
					S.push_back(a[i] + S[j]);
					found[a[i] + S[j]] = true;
				}
			}
		}
	}

	fout << S.size() + 1;

	return 0;
}
→ Reply