0197MediumArrayDynamic ProgrammingKnapsack Problem0-1 Knapsack

Even Split of Crate Loads

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A dispatcher has two identical trailers standing at a loading bay and an integer array weights, where weights[i] is the weight of the i-th crate.

Every crate has to be rolled onto exactly one of the two trailers, and no crate may be left on the bay or cut apart. The bay foreman wants the two trailers to leave carrying the same total weight.

Return true if such a hand-out exists and false if it does not. A trailer is allowed to end up with any number of crates, and the crates do not have to be handed out in the order they are listed.

Examples

Example 1

Input: weights = [6, 2, 4, 8]
Output: true

Rolling the 6 and the 4 onto one trailer leaves the 2 and the 8 for the other, and both leave with 10.

Example 2

Input: weights = [7, 3, 9]
Output: false

The crates weigh 19 in total, an odd figure, so no hand-out can leave the two trailers level.

Example 3

Input: weights = [3, 3, 3, 4, 5]
Output: true

The three crates of weight 3 go on one trailer and the 4 and the 5 go on the other, and each trailer leaves with 9.

Constraints

1 <= weights.length <= 200
1 <= weights[i] <= 100

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_split_crates(weights: list[int]) -> bool:

Java

public boolean canSplitCrates(int[] weights)

The intended approach

Time O(n * S) where S is the total weightSpace O(S)

Each trailer must carry half of the grand total, so an odd total settles the question immediately. Otherwise the question becomes whether some selection of crates weighs exactly half. Track the set of half-loads that are reachable with the crates handled so far as a boolean table indexed by weight, and fold in one crate at a time. Sweeping the table downward while folding in a crate keeps every entry it reads on the previous crate's version of the table, so a crate is never used twice.

Pythonentry point: can_split_crates

def can_split_crates(weights):
    # Time: O(n * S) with S the total weight, since each crate sweeps the table once.
    # Space: O(S) for the single reachable-load table.
    total = sum(weights)
    if total % 2 != 0:
        return False
    half = total // 2
    reachable = [False] * (half + 1)
    reachable[0] = True
    for crate in weights:
        for load in range(half, crate - 1, -1):
            if reachable[load - crate]:
                reachable[load] = True
        if reachable[half]:
            return True
    return reachable[half]

The obvious version

Recursively try both trailers for every crate and see whether any full hand-out lands half the total on the first trailer. Exponential, no table involved.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_split_crates(weights):
    total = sum(weights)
    if total % 2 != 0:
        return False
    half = total // 2
    n = len(weights)

    def walk(index, remaining):
        if remaining == 0:
            return True
        if remaining < 0 or index == n:
            return False
        if walk(index + 1, remaining - weights[index]):
            return True
        return walk(index + 1, remaining)

    return walk(0, half)

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in