Consider a knapsack-like problem where there is a set of items, and each item has a cost $c_i$ and value $v_i$. The goal is to find a subset $S$ that minimizes $\sum_{i\in S}c_{i}$ with the constraint that $\sum_{i\in S}v_{i}\geq b$) where $b$ is some arbitrary value.
This is obviously very similar to the knapsack problem, but I haven't been able figure out a way to reduce the knapsack problem to it using a polynomial time transformation on the inputs due to the inequality constraint. Maybe I'm just confused on how reductions are done.
The 0-1 knapsack problem is defined as follows:
Maximize $\sum_{i=1}^nv_ix_i$ subject to $\sum_{i=1}^nw_ix_i \leq W$, $x_i\in\{0,1\}$ where $n$ is the number of items, $\mathbf{v}$ are item values, $\mathbf{x}$ indicates whether an item is put into the knapsack, $\mathbf{w}$ are the weights of items, and $W$ is the maximum weight the knapsack can hold.
Best Answer
Since both are optimization problems, you are talking about the NP-hard knapsack problem, not the NP-complete one, because only decision problems (or decision version of optimization problems) can be NP-complete. See the wiki page for Knapsack problem for definitions.
The standard reduction when working with NP-hard problems is the Turing reduction, not the Many-one reduction which is used inside NPC. The key difference are:
whether you are allowed to call the oracle which solves the knapsack-like problem more than once (Turing reduction: yes, Many-one reduction: no)
when you are allowed to call the oracle (Turing reduction: not limited, Many-one reduction: only at the end of computation)
whether you can modify the results returned by the oracle before returning (Turing reduction: yes, Many-one reduction: no).
As @dtldarek said, it doesn't seem easy to find a many-one reduction between the two problems, where only transformation on the inputs are allowed, but it's possible to solve either one with multiple calls to an oracle solving the other (thus a Turing reduction).
Solving Knapsack-like using Knapsack: Note that for increasing total cost C, the maximal total value is non-decreasing. This property allows binary search:
Binary search for the total cost C (in range $[0,\sum c_i]$), and check (using the oracle to Knapsack) whether it's possible to achieve a total value $\ge b$. Choose either half according to the result. The smallest C can be found with small modification to binary search.
Solving Knapsack using Knapsack-like: Similar property holds: for increasing total value, the minimal cost (weight) is non-decreasing. So a similar algorithm is easy to find.