Polynomial Time Boolean Satisfiability

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 4.0s
Memory limit: 512M

Authors:
Problem types

The boolean satisfiability problem is a famous problem in computer science. You are given 2^N booleans, and a list of N numbers. A boolean is satisfied if a subset from the N numbers sum up to less than or equal to K. What is the maximum number of booleans that can be satisfied?

Note: the empty subset sums up to 0.

Input Specification

On the first line, there are two integers N, and K, separated by a space.

On the second line is a space separated list of the N integers.

Each line is followed by one line feed character (ASCII code 0x0a).

There are no trailing spaces or empty lines.

Output Specification

One integer, the number of subsets that sum to less than or equal to K.

Constraints

For all subtasks:

-2^{31} \le n_i < 2^{31}

-2^{31} \le K < 2^{31}

For all subset sums, k_i, -2^{31} \le k_i < 2^{31}.

1 \le N \le 49

Subtask 1 [2/15]

N \le 20

Subtask 2 [7/15]

K = 1

Subtask 3 [6/15]

No additional constraints.

Sample Input 1

10 10
8 2 10 10 6 1 10 10 1 5

Sample Output 1

33

Sample Input 2

5 5
1 2 3 4 5

Sample Output 2

10
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation.

Comments

There are no comments at the moment.