Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset

Question

I am working on a problem defined as the following

Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our resources and $G$ is our necessary minimal reward, is there a set $R' \subseteq R$, so that $\sum_{(z,g)\in R'}z \leq Z$ and $\sum_{(z,g)\in R'}g \geq G$?

I want to show its NP-completeness and have shown that it is in NP already. I am struggling with the NP-hardness. My known NP-hard problems are the SAT, 3SAT, partition, subset sum and bin packing.

My struggle seems to be mostly with the fact that we have to balance two different values now, the cost and the reward. This is not the case in any of the set related problems I mentioned and I am unable to think of how to model this in SAT or 3SAT. What am I missing here? How can I show the NP-hardness and as such the NP-completeness of this problem using only these given problems?

Answer 1

This sounds to me like the Knapsack problem where

• $z$ is the weight of each item,
• $Z$ is the capacity of the knapsack,
• $g$ the value of the item, and
• $G$ the value to be achieved.

The problem is NP-complete but solvable, using dynamic programming, in pseudo-polynomial time $O(n \cdot W)$ where $W = \max_{(z,g) \in R}(g)$.

You can prove that the Knapsack Problem is NP-complete by reducing from the Subset sum problem. Indeed, Subset Sum is a special case of Knapsack where $z = g$; The "weight" of each problem is the same as its "value".