Problem Statement
In the mysterious country of Byteland, everything is quite different from what you'd normally expect. In most places, if you were approached by two mobsters in a dark alley, they would probably tell you to give them all the money that you have. If you refused, or didn't have any - they might even beat you up.In Byteland the government decided that even the slightest chance of someone getting injured has to be ruled out. So, they introduced a strict policy. When a mobster approaches you in a dark alley, he asks you for a specific amount of money. You are obliged to show him all the money that you have, but you only need to pay up if he can find a subset of your banknotes whose total value matches his demand. Since banknotes in Byteland can have any positive integer value smaller than one thousand you are quite likely to get off without paying.
Both the citizens and the gangsters of Byteland have very positive feelings about the system. No one ever gets hurt, the gangsters don't lose their jobs, and there are quite a few rules that minimize that probability of getting mugged (the first one is: don't go into dark alleys - and this one is said to work in other places also).
Input
The first line contains integer t, the number of test cases (about 100). Then t test cases follow. Each test case starts with n, the number of banknotes in your wallet, and m, the amount of money the muggers asked of you. Then n numbers follow, representing values of your banknotes. Your wallet does not hold more than 20 banknotes, and the value of a single banknote is never more than 1000.Output
For each test case output a single line with the word 'Yes' if there is a subset of your banknotes that sums to m, and 'No' otherwise.Example
Input: 5 3 3 1 1 1 5 11 1 2 4 8 16 5 23 1 2 4 8 16 5 13 1 5 5 10 10 20 132 17 6 4 998 254 137 259 153 154 3 28 19 123 542 857 23 687 35 99 999 Output: Yes Yes Yes No Yes
Explanation: For example, in the last case you have to pay up, since: 6+3+123=132.
Problem Link : MARCHA1
The idea :
The idea is to find whether there exists a valid subset whose sum is equal to a given number. Now there is a dynamic programming approach to this . However what I used is the bitwise approach.
The bitwise approach :
We all know the concept of a boolean hash . Here a 0 or false means that a number is not included and 1 means that a number is included.
Now instead of using an array for hashing purpose we may use a number. An array of size 'n' may be easily replaced by a number with 'n' no of bits. So a number 2 or '10' would mean that the element corresponding to 1 is present and element corresponding to 0 is not taken.
So now all we need to do is generate all possible combination of 'n' bits . Now this can be done easily by iterating from 0 to 2^n-1. And we would add each element if it is present i.e it's corresponding digit is 1. Else we would simply not add it. Now we just have to compare with the given sum.
Now, the limit on the number of banknotes is 'n'. Let us see how many
subsets exist for these banknotes. For finding the number of subsets,
we see that for every banknote, we have two choices, either to choose it
in our calculation for the sum of notes or to ignore it in calculating
the sum. Thus, we have 2 options per banknote and 'n' banknotes. So, the
total number of subsets thus becomes 2^n where ^ represents the power operation. The number of subsets are small enough for us to bruteforce through them and the program to run in time.
An interesting way to generate all subsets of 'n' objects
when 'n' is considerably small (n <= 20) is to use the properties of
how unsigned integers are stored. Consider the number 2^n. This number
is represented in binary form as '10000...0', that is, 1 followed by n
0s. Also, any number containing a 1 at the some position will surely be
greater than 2^n. Thus, all numbers below 2^n do not have a 1 in a
position greater than or equal to 'n' starting from the LSB. By
induction, we can do the same for values of n = n-1 and n-2 and so on.
Thus, we can see that any number between 2^(n-1) and 2^n will have a 1
in the position n-1. Extending this logic, we can say that if we
consider the numbers from 1 to 2^n, we would be considering all possible
ways in which we can choose some objects from 'n' objects.
For example, consider n = 3, so 2^n = 8. Let us list 'i' and its binary representation
i Binary representation using 'n' bits
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
i Binary representation using 'n' bits
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
As you can see, if we consider that 1 means that we have selected
object at that position and 0 means that we have not selected the object
at that position, we can get all possible subsets of 'n' objects by
looping over numbers from 1 to 2^n.
For calculating the sum of the subset represented by 'i', we loop
from 0 to 'n' and we check whether the corresponding bit is set in the
value for 'i' or not. If it is, we include that object in calculating
our sum else we don't. In this way, we can get the sum for all possible
subsets of the 'n' objects.
This is exactly what we need for this problem. After taking in the
number of objects, we loop 'i' from 1 to 2^n incrementing the value of
'i' by 1 at every stage to give us a new subset. Then for a particular
value of 'i', we loop 'j' from 0 to n and check if the bit at that
particular value is set or not. Languages like C / C++ provide bit-wise operators for leftshift and rightshift.
For checking if the bit is set at position 'j'(starting from 0) we can
just check if the value of (i & (1<<j)) is 0. If it is 0, then
the bit is not set, while if it is greater than 0, then the bit is set.
Alternatively, we can also loop from 0 to n and at each stage check
whether 'i' modulo 2 is equal to 1 or not. If it is 1, then the bit at
that position is set, else it's not. Then we divide 'i' by 2 and
proceed. At the end of the 'n' iterations, 'i' will equal 0. The problem
with this appraoch is that the modulo operations take much more time
compared to the bitwise operations. Thus, now that we know how to check
if the bit is set, we initialize a value 'sum' equal to 0 at the start
of the 'n' iterations for a value of 'i' and if the bit at position 'j'
is set, we add the corresponding banknote value to 'sum' else we don't.
At the end of these iterations, we check if the value of 'sum' equals
the required value. If it does, then we have found a subset with the
required sum and so we print a "Yes" and exit. Else, if at the end of
2^n iterations of 'i' we don't have a subset with the required sum, then
we print a "No" and exit.
The program should look something like this :
[code]
Start
Take in the value of 'n' and the required value of sum 'm'
Take in all the values for the banknotes in array 'd[]'
For i = 1 and i < (2^n)
sum = 0
For j = 0 and j < n
if jth bit of i is set
sum = sum + d[j]
if sum equals m
print Yes and return
Print No and return
Take in the value of 'n' and the required value of sum 'm'
Take in all the values for the banknotes in array 'd[]'
For i = 1 and i < (2^n)
sum = 0
For j = 0 and j < n
if jth bit of i is set
sum = sum + d[j]
if sum equals m
print Yes and return
Print No and return
[/code]
No comments:
Post a Comment