CODEM5 - Problem5
You are given an array of weights of n objects and your task is to select minimum number of objects whose sum of weights is exactly equals to some given k.
Input
Line 1 - number of test cases T (<= 10) followed by 2 lines for each test case
Line 2 - Number of objects n (<= 20) and total weight k (<= 10^4)
Line 3 - weights (<= 10^4) of n objects (each separated by space)
Output
Minimum number of objects whose weights sums to k.
Example
Input: 2
5 9
10 9 4 3 5
3 7
1 2 3 Output: 1
impossible
Explanation
For the first case the two combinations are possible: (9), (4, 5) hence minimum number of objects is 1.
For the second case there are no combinations possible hence impossible.
hide comments
Himanshu Sharma:
2016-09-12 10:07:24
HELL, bug in test data take n =100 :-| |
|
lumaere:
2016-04-05 21:18:25
The number of objects is way too low for the time limit allotted. Can finish with brute force. |
|
Xiaomin Zhang:
2016-03-07 09:41:13
there is some case that n>20..... and the bug of the test data, just almost drives me crazy with so many wrong answer! |
|
:.Mohib.::
2015-06-18 06:29:34
Awsm que... should be in classical.. |
Added by: | Bhavik |
Date: | 2014-02-04 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem(for CODE MARATHON) |