1
$\begingroup$

I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below.

A cashier only has x time to scan a person's goods. The goods come 1 item per time step in a conveyor belt. In one time step, the cashier can either scan an item or bag the item (so when bagging, the cashier misses the item on the conveyor belt for that time step). The place to hold scanned, unbagged goods has a max capacity of c, where each good takes 1 unit space. However, once the cashier starts to bag scanned items, the cashier must bag all unbagged scanned items. The cashier also wants to ensure he makes the most money possible. How would the cashier go about choosing the goods such that he maximizes the amount of money the buyer spends. What is the maximum amount of money the cashier can make?

This seems to be a modification of the 0-1 knapsack problem, where the max capacity c is the max capacity of the knapsack, the price of the item is its value in the knapsack, and all items have a 1 unit space. I am, however, confused about how I would incorporate the "conveyor belt" of missing items and the moving of items out of c into the algorithm. I imagine this could still be run in $O(nc)$ time with $O(c)$ space complexity (in fact the original problem statement says it should be possible in these bounds). How would I go about modifying the 0-1 knapsack problem for this?

$\endgroup$
4
  • $\begingroup$ Please credit the original source of this task. $\endgroup$
    – D.W.
    Sep 29, 2020 at 1:27
  • $\begingroup$ @D.W. - a random paper I found at the university library (with some notes a la knapsack) but that seems so random people will unnecessarily start doubting it in the comments $\endgroup$ Sep 29, 2020 at 1:36
  • 2
    $\begingroup$ @ztn78420eoopy This random paper probably has a title and authors you can cite, no? Or do you mean literally a piece of paper? $\endgroup$
    – orlp
    Sep 29, 2020 at 1:43
  • $\begingroup$ @orlp - no literally a random piece of paper with this scribbled on that I happened to see and it is now taking up way too much of my time $\endgroup$ Sep 29, 2020 at 2:41

1 Answer 1

1
$\begingroup$

Let the $i$th item have profit $p_i$, and assume there are $n$ items passing by.

We can construct a graph where the nodes are pairs $(k, b)$ where $k$ is the number of timesteps, and $b$ is the number of items in our bagging area. We have $0 \leq k \leq x$ and $0 \leq b \leq c$.

Then, avoiding invalid nodes and/or nonsensical self-edges,

  1. Add edges from $(i-1, b)$ to $(i, b + 1)$ with weight $-p_i$. These represent scanning an item.

  2. Add edges from $(i, b)$ to $(i + 1, b)$ with weight $0$ for all $i$. These represent skipping an item.

  3. Add edges from $(i, b)$ to $(i + b, 0)$. These represent bagging all scanned items.

Now we have a directed weighted acyclic graph, in which we can find the longest path in linear time. And the longest path between $(0, 0)$ and $(x, 0)$ precisely gives us the maximum profit (and following the path also gives us the steps used).

There are $O(cn)$ edges, and thus that is our complexity.

$\endgroup$
1
  • $\begingroup$ right but this would take more than the $O(c)$ space that the knapsack problem modification would, no? $\endgroup$ Sep 29, 2020 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.