I know of the knapsack problem. I want to find an algorithm that "inverts" the knapsack problem. My problem is as follows:
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is greater than or equal to a given limit and the total value is as small as possible.
$$\min \sum _{i=1}^{n}v_{i}x_{i}$$ subject to
$$\sum _{i=1}^{n}w_{i}x_{i}\geq W $$
Is it still NP-hard problem?
I think the answer is yes, if the # of each item is bounded. Suppose you have two bags, namely, $B_1$ and $B_2$ and you want to distribute the items into these two bags. You want to determine the # of each item to include in $B_1$ such that $$ \sum_{i=1}^n v_ix_i $$ is minimized and at the same time, $$ \sum_{i=1}^n w_ix_i \geq W $$ This is equivalent to determining the # of each item to include in $B_2$ such that $$ \sum_{i=1}^n v_ix_i $$ is maximized and at the same time, $$ \sum_{i=1}^n w_ix_i \leq W' $$ where $W' = \text{total weights of the items } - W$.