I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below.
A cashier only has
xtime 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?