I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the following DP relations
#number of ways to get sum using subsets of {1, 2, ..., i}
dp[i][sum] += dp[i - 1][sum] #not using element i
dp[i][sum + array[i]] += dp[i - 1][sum] #using element i
Constraints:
1 <= n <= 30
1 <= array[i] <= 1e9
0 <= limit <= 1e9
Time: 1s
Memory: 64 Mb
At first I considered using plain array( or std::array
, whatever) but an array dp[30][1e9 + 1]
can't be allocated on stack and heap allocation would be too expensive given time limit of 1
second. I came up with the following implementation using std::unordered_map
:
std::unordered_map<int, int> dp;
for (int element_idx = 0; element_idx < i_size; ++element_idx) {
if (arr[element_idx] > limit) {
continue;
}
std::unordered_map<int, int> new_sums;
new_sums[arr[element_idx]] = 1;
if (!element_idx) {
dp = std::move(new_sums);
continue;
}
for (std::pair<int, int> &sum_count : dp) {
new_sums[sum_count.first] += sum_count.second;
}
for (std::pair<int, int> &sum_count : dp) {
if (sum_count.first + arr[element_idx] <= limit) {
new_sums[sum_count.first + arr[element_idx]] += sum_count.second;
}
}
dp = std::move(new_sums);
}
The problem it that this implementation runs into a memory limit error. Moreover, my computer just freezes if the input is 30 distinct 6-, 7-digit integers. I am pretty sure there is nothing wrong with my algorithm and the only problem my poor algorithm implementation experience and C++ knowledge.
int
s are far to small here, you should uselong
s orlong long
s \$\endgroup\$ – Yk Cheese Sep 20 '17 at 19:52n
you want to know how many different subsetsS
of{1, … n}
you can find such that that the sum of elements does not exceed the limit, i.e.sum(S) <= limit
? So in total it issize({S subset {1, …, n} if sum(S) <= limit})
? \$\endgroup\$ – Martin Ueding Sep 20 '17 at 20:00int
is enough here because every time I add a value to map I check whether it is less than or equal to limit which, in its turn, is always less than or equal to1e9
which fits inint
on both my and my online judge's machines. Thanks for your advice anyway! 2) @Martin Uedingsize({S subset {1, …, n} if sum(S) <= limit})
is indeed what I am looking for. The part 'for eachn
' is unnecessary though. \$\endgroup\$ – Atin Sep 20 '17 at 20:12