I have a set of $K$ keywords. Each of this keywords can have a set of bids from $1\$,\ldots, N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost are monotonic in bids. Now, the problem is:
Select a bid for each of the keyword such that overall clicks across the keywords are maximized such that the cost is still within a given budget $B$. Let $\text{Clicks}(W_i)$ and $\text{Cost}(W_i)$ denote the clicks and cost on the keyword $i$. Then (informally) the problem is to select a value of bid for each keyword such that \begin{align}\max\sum_{i=1}^{K}&\text{Clicks}(W_i) \\s.t.&~~\sum_{i=1}^{K}\text{Cost}(W_i)\leq B\end{align} Is this a type of knapsack problem? Are there any known heuristic in the literature.
Following is not important for the question (and thus can be skipped), but is for the curious ones to know how I am solving this currently.
Let $S_{ij}$ denote the cost for using bid $j$ for keyword $i$ and let $C_{ij}$ be the clicks for the same. Let $x_{ij}$ be the indicator variable for using bid $j$ for keyword $i$. Then among variables $x_{i1},\dots,x_{iN}$ only one can be non-zero (i.e. $x_{ij}=1$) whereas the rest is zero (since only one bid can chosen for keyword).
Thus, the whole problem can be formulated mathematically as
\begin{align}\max_{x_{ij}}~&\sum_{i=1}^{K}\sum_{j=1}^{N}x_{ij}C_{ij} \\s.t.~~\sum_{i=1}^{K}\sum_{j=1}^{N}&x_{ij}S_{ij}\leq B\\\sum_{j=1}^{N}x_{ij}=1&~~\forall i\in \{1,\dots,K\}~~,~~x_{ij}\in\{0,1\}\end{align}
Last, two constraints ensure they are indicator variables and only one bid is chosen for a given keyword. Solving this should solve the original problem.
