Bags
InterviewTime limit1sMemory limit1024 MB
For each data set, find the fewest items whose weights sum exactly to the target, or report Not possible if no such subset exists.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Array
- Solved
- No attempts yet
Problem
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 makes guests feel they are receiving a lot without using 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.
Input
The first line contains a single integer n, the number of data sets. Each data set is three lines. The first line of a data set is a single integer x, the number of items. The next line contains x integers, the weight of each item. The last line of a data set is a single integer, the total weight you are trying to reach.
Output
For each data set, output the smallest number of items whose weights add up exactly to the target weight. If it is not possible to add up exactly to the target weight, print Not possible.