← 返回 airbnb 的题目列表Minimum Purchases to Fill an Exact Target Amount
类型：online_judge
Problem: Minimum Purchases to Fill an Exact Target Amount
Given a target amount target and n item prices prices, each item can be purchased unlimited times.
Compute:
Whether it is possible to purchase some items whose total price is exactly target;
If possible, the minimum number of items needed;
Also print any one purchase combination that achieves this minimum count.
If it is impossible to make the exact target amount, print -1.
All amounts are integers, for example in cents, to avoid floating-point precision issues.
Input Format
n target
p1 p2 ... pn
n is the number of item types;
target is the target amount;
prices[i] is the price of the i-th item;
Each item can be used unlimited times.
Output Format
If the target cannot be formed exactly:
-1
If the target can be formed, output two lines:
min_count
price_a price_b price_c ...
The second line is any valid minimum-size purchase combination. The order does not matter.
Constraints
1 <= n <= 100
1 <= prices[i] <= target <= 100000
Each item can be purchased unlimited times.
Example
Example 1
Input:
3 11
1 5 7
Output:
3
5 5 1
Explanation: 5 + 5 + 1 = 11, using 3 items, which is minimum.
Example 2
Input:
2 3
2 4
Output:
-1
Explanation: It is impossible to form 3 using prices 2 and 4.
Example
Input
3 11
1 5 7
Output
3
5 5 1