Fewest Warehouses to Ship an Order

hard

Backtracking Bit Manipulation Dynamic Programming

When an order contains items stocked in different fulfilment centres, it ships as several packages, and every extra package is a cost to the store and a worse experience for the shopper, who gets their order in pieces. The splitting service must choose which warehouses fulfil an order.

The order contains itemCount distinct items, numbered 0 to itemCount - 1. Warehouse w can supply the items listed in stocks[w] (every one of them, in the quantity ordered) and charges costs[w] to ship one package. Each chosen warehouse ships exactly one package, containing whichever of the order's items it is assigned.

Choose a set of warehouses that together can supply every item. First minimise the number of packages; among the choices with that fewest number, minimise the total shipping cost.

Return [packages, cost], or [-1, -1] if no choice of warehouses can supply the whole order.

Example

itemCount = 3, stocks = [[0,1],[1,2],[2],[0]], costs = [5,4,1,1].

No single warehouse has all three items, so at least two packages are needed. Warehouses 1 and 3 together supply items 1, 2 and 0 for a cost of 4 + 1 = 5, the cheapest of the two-package options (0 and 2 would cost 6). The answer is [2, 5]. Three packages from cheaper warehouses would not be better: fewer packages always wins.

Example 1

Input

[
  "3",
  "[[0,1],[1,2],[2],[0]]",
  "[5,4,1,1]"
]

Output

[2,5]

Explanation. The example.

Example 2

Input

[
  "3",
  "[[0],[1]]",
  "[1,1]"
]

Output

[-1,-1]

Explanation. Nobody stocks item 2.

Example 3

Input

[
  "2",
  "[[0,1],[0],[1]]",
  "[100,1,1]"
]

Output

[1,100]

Explanation. One package beats two cheaper ones.

Example 4

Input

[
  "1",
  "[[0],[0],[0]]",
  "[7,3,9]"
]

Output

[1,3]

Explanation. The cheapest of several complete warehouses.

Example 5

Input

[
  "4",
  "[[0,1],[2,3],[0,2],[1,3],[0,1,2]]",
  "[3,3,2,2,10]"
]

Output

[2,4]

Explanation. Several two-package covers; warehouses 2 and 3 are the cheapest.

Example 6

Input

[
  "5",
  "[[0,1],[2],[3,4],[1,2,3],[0,4]]",
  "[1,1,1,5,5]"
]

Output

[2,10]

Explanation. Three cheap warehouses would cost 3, but two packages win.

Example 7

Input

[
  "2",
  "[[],[1],[0],[]]",
  "[1,2,3,4]"
]

Output

[2,5]

Explanation. Warehouses with nothing to offer are ignored.

Example 8

Input

[
  "6",
  "[[0,1,2],[3,4,5],[0,3],[1,4],[2,5],[0,1,2,3,4,5]]",
  "[4,4,1,1,1,9]"
]

Output

[1,9]

Explanation. A single warehouse with everything.

Example 9

Input

[
  "4",
  "[[0],[1],[2],[3]]",
  "[1,2,3,4]"
]

Output

[4,10]

Explanation. Every item comes from its own warehouse.

Example 10

Input

[
  "5",
  "[[0,1,2],[2,3,4],[0,3],[1,4],[0,1,2,3],[4]]",
  "[6,6,3,3,8,2]"
]

Output

[2,10]

Explanation. Several pairs cover everything; warehouses 4 and 5 are the cheapest pair.

Follow-up: Real orders also have quantities: warehouse `w` holds `q[w][i]` units of item `i`, and an item may be split across warehouses. Does the bitmask still describe a state, and if not, what would you search over instead?

Constraints:

- `1 <= itemCount <= 15` - `1 <= stocks.length == costs.length <= 40` - `0 <= stocks[w].length <= itemCount`, and the items in `stocks[w]` are distinct values in `[0, itemCount)`. - `1 <= costs[w] <= 1000`

Views: 2