Vault Split Weight Target
Preview mode. Log in to edit, run, submit, and save progress.
Vault Split Weight Target
A secure-logistics firm is dispatching an armored truck from its central vault. The truck's suspension is calibrated for a target load of $T$ kilograms: every kilogram above or below the calibration adds strain on the axles and draws unwanted attention at weigh stations. Inside the vault sit $N$ sealed crates, the $i$-th weighing $W_i$ kilograms. Each crate must be taken whole or not at all, and the dispatcher may load any subset of the crates - including sending the truck out completely empty. If the chosen crates weigh $S$ kilograms in total, the strain of the run is $|S - T|$. Pick the subset that minimizes the strain and report the minimum possible value of $|S - T|$. ### Function Description Complete the function `closestVaultLoad` provided in the editor. The function receives the following parameters:
| Parameter | Type | Description |
|---|---|---|
| $N$ | integer | the number of crates in the vault |
| $T$ | integer | the truck's calibrated target load |
| $W$ | array of integers | $W_i$ is the weight of the $i$-th crate |
The function must return a single integer - the minimum achievable value of $|S - T|$, where $S$ is the total weight of the loaded subset. ### Input Format - The first line contains two space-separated integers $N$ and $T$. - The second line contains $N$ space-separated integers $W_1, W_2, \ldots, W_N$. ### Output Format Return a single integer: the minimum possible value of $|S - T|$ over all $2^N$ subsets of crates. ### Notes - The empty subset is allowed: an empty truck has $S = 0$ and strain $|0 - T| = T$. - Each crate can be loaded at most once, and crates cannot be split. - Totals can reach $3.8 \times 10^{10}$, so use a 64-bit integer type for sums (`long long` in C++, `long` in Java).
Examples
```text 5 16 7 3 9 12 2 ```
```text
Explanation: Loading the crates weighing $7$ and $9$ gives $S = 7 + 9 = 16$, so the strain is $|16 - 16| = 0$. The target is hit exactly, and $0$ is the best possible answer.
Approach hint
$2^{38}$ subsets is roughly $2.7 \times 10^{11}$ - enumerating them all is far beyond any time limit. But $2^{19}$ is only about half a million. Can you cut the problem in two?
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.
```text
5 16
7 3 9 12 2
``````text