# Optimisation problem : How to solve a Knapsack problem with boolean variables? Is this problem considered a multi-choice Knapsack problem?

I am trying to solve an optimization problem, that it's very similar to the knapsack problem but it can not be solved using the dynamic programming. The problem I want to solve is very similar to this problem:

Given a set of products, i.e. $P = \bigcup_{i=1}^{n}P_{c_{i}}$ where each $P_{c_i}$ is the set of products that belong to the category $c_i$. Also we split each category $c_{i}$ as $\{\ G_{c_{i1}},...,G_{c_{ik}} \}\$ where each group of products $G_{c_{ij}}$ contains products that belong to the same group or sub-category. We want to pick one product from each group and give preference to products that the user is interested in.

Our goal is to create a user basket $Z$, $Z \subset P$, which satisfies the following properties:

1. Personalization : The basket should contain products that are relevant to the user profile. We model our user profile as first $U_c$, a boolean vector $U_c= \{\ u_{c1},...,u_{cn} \}\$, where $u_{c_{i}}$ is a boolean value that indicates whether the user $u$ is interested in a particular category $c_{i}$ or not. Second as $U_G= \{\ u_{g1},...,u_{gm} \}\$. The final user basket $Z$, should maximize the coverage of categories and groups the user is interested in.
2. Budget: A basket should have a maximal budget. It captures the maximum amount of money a user is willing to pay. To this regards we set a threshold on the maximum budget of the basket $\delta_{b}$. Which means that $\sum_{z \in Z} price(z) \leqslant \delta_{b}$.

We can than model this problem as an optimization problem:

\begin{align} & & & max( \sum_{c \in C} x_{c}*u_c + \sum_{c \in C} \sum_{g \in G_c} u_g* x_{g} * u_c ) \\ % & \text{subject to} & & \sum_{z \in Z} price(z) \leqslant \delta_{b} \\ % &&& \end{align}

Where:

• $x_{c}$ is a boolean that captures whether category $c$ is covered in Z or not, it equals to 1 if the category is not covered and 0 otherwise.
• $x_g$ is a boolean that captures whether group $G$ is covered in Z or not, it equals to 1 if the group is not covered, and 0 otherwise.

• $u_g$ captures the user interest in the group of product G.

• $\delta_{b}$ is an adjustable parameter to control the maximum user budget.

The Figure below gives an example of the problem we want to solve. The categories are the principle nutrients for example:

• $c_1$=Carbs, $c_2$=Protein etc.
• The groups are for example for protein $G_{c_{21}}=Meat, G_{c_{22}}= Milk$.
• The user profile can be: $U_c= \{\ Carbs=1,Protein=1,Fat=0\}\$, and $U_G= \{\ Meat=0.1, Milk=0.2, Pasta=0.1, Bread=07, Oil=0.01, Butter=0.6,\}\$

For example:

• We suppose that $user_1$ has the following profile $U_c= \{\ Carbs=1,Protein=1,Fat=0\}\$, and $U_G= \{\ Meat=0.8, Milk=0.2, Pasta=0.1, Bread=1, Oil=0.01, Butter=0.6,\}\$ and his budget is 3 dollars. The best basket for him would be {Product11, Product21,Product41}.
• Whereas for $user_2$, having the following profile $U_c= \{\ Carbs=1,Protein=1,Fat=0\}\$, and $U_G= \{\ Meat=0.8, Milk=0.2, Pasta=0.1, Bread=1, Oil=0.01, Butter=0.6,\}\$ and his budget is 2 dollars. The best basket for him would be {Product11, Product41} because we won't choose a product from the second group of the protein category (i.e. Milk) because we want to maximize the sum of categories the user is interest in.

The dynamic programming can not be used for this problem because we change the sum of the values at every combination using the $x_c$ and $x_g$ variables. Until now I don't know under which mathematical problem this falls into. Any help or orientation would very much appreciable.