KnapsackTweak
SRM 821 · 2022-01-07 · by misof
Problem Statement
Time limit is 4 seconds.
There is a collection of items for sale, their prices are given in the
We would love to have a subset of items such that its total price is exactly target.
We are allowed to tweak the prices of items. The smaller the maximum change, the better. The new prices must be integers but they may be negative.
Find and return the smallest non-negative X with the following property: it is possible to adjust the price of each item by at most X in such a way that there will be a subset of items with sum exactly equal to target.
Constraints
- items will contain between 1 and 50 elements, inclusive.
- Each element of items will be between 1 and 10^5, inclusive.
- target will be between 1 and 10^5, inclusive.
{11, 21, 31, 41, 51}
150
Returns: 1
The best we can do is make all items one cheaper.
{11, 21, 31, 41, 51}
154
Returns: 1
The best we can do is make one item cheaper by 1. Or three items cheaper by 1 and the other two more expensive by 1.
{11, 21, 31, 41, 51}
73
Returns: 0
We can reach the target using the current prices (11 + 21 + 41) so no tweaking is needed.
{100000, 99999, 99997, 99998}
1
Returns: 99996
{100, 100, 100, 100, 100000}
383
Returns: 5
{2, 8, 70}
50
Returns: 10
The best solution is to tweak all three prices: to {-8, -2, 60}.
Submissions are judged against all 93 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class KnapsackTweak with a public method int smallest(vector<int> items, int target) · 93 test cases · 2 s / 256 MB per case