# Is this a knapsack problem?

I have a set of $$K$$ keywords. Each of this keywords can have set of bids from $$1\,\dots,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 this

Select a bid for each of the keyword such that overall clicks across the keywords is 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 known heuristic in 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 ensures they are indicator variables and only one bid is chosen for a given keyword. Solving this should solve the original problem.

• I'm looking at your problem statement and seem to be unclear about some details. What does $W_i$ represent? Are you saying that each keyword can only have one bid assigned to it and this bid can be assigned to all the keywords if you wanted? – spektr Dec 12 '18 at 1:47
• I'm not sure how the bids factor into this either. – Richard Dec 12 '18 at 5:20
• Apologize for the mistaken used of notation. I thought it was clear from the context. $W_i$ is just an index for keyword $i$. Each keyword can have a different value of bid for itself. You can imagine a matrix with rows as keywords and columns as possible bid values. Then this problem becomes, choose a column for every keyword such that overall clicks is maximized when spend is within the budget. – dineshdileep Dec 12 '18 at 6:03
• @dineshdileep okay, so $W_i$ is an index value corresponding to a bid choice for keyword $i$, correct? If so, I now see what you’re trying to do and how it relates to your formulation at the bottom. So your question is just if this is a knapsack problem and not about a fast algorithm to solve it? What are you doing to solve your latter formulation? – spektr Dec 12 '18 at 13:20

Yes, you are optimizing a knapsack problem.

The objects, or "items" in most knapsack problem (KP) definitions, in your case is a set $$S=\{s_{00}, s_{01}, ..,s_{0n}, s_{10}, .. s_{kn}\}$$, which contains composite keyword-bid pairs, so $$s_{ij}$$ denotes an object labeled "keyword $$i$$ bid $$j$$". The reason you should think of your items as composite this way is that the benefit/cost values (clicks/costs in your post, respectively) are attached to keyword-bid pairs.

The clicks and fee associated with each $$s_{ij}$$ are:
- $$c_{ij}$$: the number of clicks for "keyword $$i$$ at bid $$j$$" composite object, and
- $$f_{ij}$$ is the fee you pay for that keyword-bid combination (I avoided using "C"ost not to confuse it with "C"licks).

You can now feed your clicks $$C$$, the corresponding fees $$F$$, and threshold $$B$$ to any knapsack solver to find the optimal solution (this is a good one if your $$B$$ is a reasonably small).

You can prove that your problem is a knapsack problem (KP) by reducing KP into your problem (creating a mapping that can transform any KP instance to a corresponding instance of your problem). Following KP's definition here:

• KP's items map to your $$S$$
• KP's values map to your clicks
• KP's weights map to your fees (you called them costs).
• KP's capacity maps to your budget $$B$$.

It appears that the original statement is essentially a slight generalization of the Knapsack Problem since you assume your functions $$\text{Clicks}(\cdot)$$ and $$\text{Cost}(\cdot)$$ can be any monotonic functions, instead of the linear functions seen in the traditional Bounded Knapsack Problem assumes.

I think one can be sure that this is at least as hard as the Knapsack Problem. I don't know what values for $$K$$ and $$N$$ you have, but this can certainly be solved exactly using dynamic programming (DP). The main issues you may run into is if $$N = O(2^K)$$. If $$N$$ is instead polynomial in $$K$$, you should be able to solve this problem in polynomial time and space using DP pretty readily.