Bags
면접 대비시간 제한1초메모리 제한1024 MB
각 테스트마다 목표 무게와 정확히 일치하도록 아이템을 고를 때 필요한 최소 개수를 구하고, 불가능하면 Not possible을 출력한다.
문제
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.