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
asifalim:
2021-04-27 11:56:16
after(6) keeping a visited array got accepted!
|
|
scolar_fuad:
2019-10-12 19:44:42
knapsake in enough to solve this problem ...
|
|
subhikhalifeh:
2019-05-04 00:43:44
D:
|
|
kaneki0530:
2018-06-06 11:10:31
Backtracking!!! AC in one go |
|
thanos_tapras:
2018-04-27 12:47:27
Tried with subset sum, but always WA. Tried again with bitmasks and got AC |
|
prince_batra:
2018-03-24 18:57:50
I try this problem Just like subset sum problem of DP with minimum coins to form the sum but still getting WA?
|
|
chetan4060:
2017-12-08 19:51:20
try bitmask if rte
|
|
mahilewets:
2017-09-09 15:33:50
Knapsack |
|
pradeep_yadav:
2017-08-26 15:44:33
Take n about 105
|
|
kshubham02:
2017-08-23 09:28:51
Buggy question, take n=100. |
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) |