<p>Yes, it is called a <a href="https://en.wikipedia.org/wiki/List_of_knapsack_problems#Direct_generalizations" rel="nofollow noreferrer">multiple-choice knapsack problem</a>. It can be solved in time <span class="math-container">$O(N B)$</span> by dynamic programming. The state of the dynamic program is given by a pair <span class="math-container">$(i, b)$</span> and the associated value is the maximum value (clicks) you can get with keywords from <span class="math-container">$1$</span> to <span class="math-container">$i$</span> with a budget at most <span class="math-container">$b$</span>.   </p>

<p>Source: S. Martello, P. Toth. <em>Knapsack Problems</em>. Wiley, 1990. </p>

CC BY-SA 4.0
2018-12-20T00:46:21.557Z
2018-12-20T00:46:21.557Z
Vincenzo
<p>I have a set of <span class="math-container">$K$</span> keywords. Each of this keywords can have a set of bids from <span class="math-container">$1\$,\ldots, N\$$</span>. 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:</p>

<hr>

<p>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 <span class="math-container">$B$</span>. Let <span class="math-container">$\text{Clicks}(W_i)$</span> and <span class="math-container">$\text{Cost}(W_i)$</span> denote the clicks and cost on the keyword <span class="math-container">$i$</span>. Then (informally) the problem is to select a value of bid for each keyword such that <span class="math-container">\begin{align}\max\sum_{i=1}^{K}&amp;\text{Clicks}(W_i) \\s.t.&amp;~~\sum_{i=1}^{K}\text{Cost}(W_i)\leq B\end{align}</span> Is this a type of knapsack problem? Are there any known heuristic in the literature.</p>

<hr>

<p>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.</p>

<p>Let <span class="math-container">$S_{ij}$</span> denote the cost for using bid <span class="math-container">$j$</span> for keyword <span class="math-container">$i$</span> and let <span class="math-container">$C_{ij}$</span> be the clicks for the same. Let <span class="math-container">$x_{ij}$</span> be the indicator variable for using bid <span class="math-container">$j$</span> for keyword <span class="math-container">$i$</span>. Then among variables <span class="math-container">$x_{i1},\dots,x_{iN}$</span> only one can be non-zero (i.e. <span class="math-container">$x_{ij}=1$</span>) whereas the rest is zero (since only one bid can chosen for keyword). </p>

<p>Thus, the whole problem can be formulated mathematically as </p>

<p><span class="math-container">\begin{align}\max_{x_{ij}}~&amp;\sum_{i=1}^{K}\sum_{j=1}^{N}x_{ij}C_{ij} \\s.t.~~\sum_{i=1}^{K}\sum_{j=1}^{N}&amp;x_{ij}S_{ij}\leq B\\\sum_{j=1}^{N}x_{ij}=1&amp;~~\forall i\in \{1,\dots,K\}~~,~~x_{ij}\in\{0,1\}\end{align}</span></p>

<p>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. </p>

<optimization>
Is this a knapsack problem?
dineshdileep
# Is this a knapsack problem?

(Asked by: username_0 on 2018-12-10)

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.

**Tags:** optimization

---

## 1 answers

### Answer by username_1 on 2018-12-20. Score: 1

Yes, it is called a [multiple-choice knapsack problem](https://en.wikipedia.org/wiki/List_of_knapsack_problems#Direct_generalizations). It can be solved in time $O(N B)$ by dynamic programming. The state of the dynamic program is given by a pair $(i, b)$ and the associated value is the maximum value (clicks) you can get with keywords from $1$ to $i$ with a budget at most $b$.

Source: S. Martello, P. Toth. *Knapsack Problems*. Wiley, 1990.


---

