I thought mathoverflow is the place for research-level stuff based on people's comments on the internet. Stachexchange seems to be not well relevant to theoretical research.

In this case, not only items in the same container have conflicts but items from different containers. I do not think that the same dynamic programming can solve this problem. This new problem becomes more like the knapsack problem with conflict graphs but showing this new problem seems to be non-trivial. The knapsack problem with conflict graphs can be shown to be strongly np-hard via reduction from the maximum independent set problem. But we cannot reduce the independent problem to this new problem I configured.

Your feedback is very helpful. I have a follow up question. Will the problem become strongly NP-hard if there exists conflict between containers such that items from different containers cannot be picked at the same time under some conditions? E.g., Suppose $I_i(C)(median)$ denotes the median weight of all items in the container containing item $I_i$, we have the constraint: if $p_j=p_k=1$ and $I_j(C)(median)\leq I_k(C)(median)$, $ \frac{I_j(C)(median)}{v_j} \leq \frac{I_k(C)(median)}{v_k}$.

I will be great if you could also know how to perform the reduction in my corrected constraint.

That is a nice reduction. Sorry I made a mistake specifying the constraint. The correct constraint should $B<\sum_h w_h<2B$. I still wanna give you a vote for answering my question. Thanks.

Thank you very much! You are a very nice person and I wish I could learn more from you.

Btw, I am very impressed by your reduction skill. How could you think of such nice reduction? Could you share some tips on doing reduction?

I got your point about the "super useful" item. But I am still a little bit confused about the correspondence establishment about multiplying $c$.

Btw, I know it is intuitive that multiplying all $w_h$ and $B$ by a parameter $c$ will not influence the solution. But it becomes tricky when you want to formalise this intuition. How can we formally show that multiplying by $c$ will result in the same solution?

Hi Max, based on my understanding of your reduction. When $\sum_{h} (w_h+v_h)/2<B$, we will never choose the useless item, and the solution of the new problem is the solution of my original problem. When $\sum_{h} (w_h+v_h)/2>B$, we will always choose the ``super useful" item and the solution of the new problem is the solution of my original problem plus the "super useful" item. But how we can make sure that the "super useful" item will be always chosen in the new problem? Otherwise, the introduced extra weight $w_*$ will impact the solution of my original problem.

@JoelDavidHamkins Thanks for pointing it out. I have updated it.

I change a little bit on the constraint. Hope that it may facilitate the problem reduction.