I'm dealing with a variant of the Knapsack problem:
Given $n$ distinct types of items, each with a value $v_i$ and weight $w_i$ (both being positive integers), we can select an infinite number of each item. The goal is to pack a knapsack with a maximum weight of $W > 0$ such that the total value of the items is maximized.
The mathematical formulation is:
\begin{equation*} \begin{aligned} & \underset{n_i}{\text{maximize}} & & \sum_{i=1}^n n_i v_i \\ & \text{subject to} & & \sum_{i=1}^n n_i w_i \le W, \\ &&& n_i \in \mathbb{N} \end{aligned} \end{equation*}
I recognize that this is the unbounded Knapsack problem, typically addressed using dynamic programming. Nevertheless, I've recently been posed this question in an interview, where the interviewer mentioned the existence of a greedy algorithm solution. Is there truly a greedy approach to solve this problem?
The intuitive approach might be to greedily select the item with the highest value-to-weight ratio, $v_i / w_i$. However, there exists a counterexample: consider $W=10$, with item 1 characterized by $v_1=7, w_1=7$ and item 2 by $v_2=4, w_2=5$. Opting for two of item 2 proves more beneficial than a single instance of item 1.
Yes sort $v_i/w_i$ in non increasing order and take the items according to that sorting until you can't take any more item.