Consider the usual bounded knapsack problem, with the extra twist: you know that $k$ of the chosen items will get spoiled after the sack is packed. And this happens adversarially, i.e. $k$ most valuable items will be gone.
Is there still a pseudo-polynomial time algorithm for such a problem? Anything else interesting that can be said about complexity in such a situation?
It looks very natural, but no relevant references turn up.
This was my question to start with, and I think I have figured out how to solve it in pseudopolynomial time. We can order the items by value, from largest to smallest, and guess what is the last (least valuable) item in this order that will get spoiled. Suppose this is the $i$-th item. Then pick $k-1$ lowest-weight items among the first $i-1$ items in this order, add the $i$-th item and subtract the total weight of these $k$ items from the capacity of the knapsack. Then solve the instance of knapsack with items $i+1, \dots, n$ and the remaining capacity. This adds a factor of $n$ to the running time of the standard knapsack algorithm. Intuitively, we are trying to minimize the capacity wasted on items that will get spoiled, under the constraint that these are the $k$ most valuable items.
