KnapsackTweak | Topcoder Archive

Problem Statement

Time limit is 4 seconds.

There is a collection of items for sale, their prices are given in the int[] items.

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.

Definition

Class:: KnapsackTweak
Method:: smallest
Parameters:: int[], int
Returns:: int
Method signature:: int smallest(int[] items, int target)
(be sure your method is public)

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.

Examples

```
{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.

{100, 100, 100, 100, 100000}

Returns: 5

```
{2, 8, 70}
```
```
50
```
```
Returns: 10
```
The best solution is to tweak all three prices: to {-8, -2, 60}.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.