| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 64 | 51 | 41 | 80.392% |
When creating a gift bag, you are trying to create a bag that weighs as much as possible with as few items as possible. This is to make it feel like the guests are receiving a lot without having to use as many items in each gift bag. Instead of finding how much to put in each gift bag, write a program that finds the fewest number of items you can put into a gift bag to reach the recommended value.
The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will be three lines, and will start with a single integer x denoting the number of items. The next line will contain x integers, indicating the weight of each item. The next line will be a single integer indicating the total weight you are trying to reach.
Output the smallest number of items that will add up to the weight to be returned. If it is not possible to add up exactly to the weight to be returned, print Not possible.
3 10 1 3 3 3 5 7 7 5 5 10 39 10 1 2 3 4 5 6 7 8 9 10 27 1 100 50
6 3 Not possible
School > PLU High School Programming Contest > PLU 2018 > Advanced 10번