Example Data
For this question, let's assume the following items:
- Items: Apple, Banana, Carrot, Steak, Onion
- Values: 2, 2, 4, 5, 3
- Weights: 3, 1, 3, 4, 2
- Max Weight: 7
Objective:
My goal is to return the optimal set while staying under the weight, which I can do treating this as a 0/1 knapsack problem. This is how I solved the initial problem with dynamic programming: https://stackoverflow.com/q/60796419/1178523
However, I also want to return suboptimal or equal sets. Say I want the top 3 best configurations of the items? This does not really seem possible from my approach using dynamic programming.
Furthermore, I would like to add additional constraints, say I want the set to include at least 1 fruit, 1 vegetable, and 1 meat (from the example).
My Question:
I'm hoping someone can point me in the right direction of what method can achieve the above. That is, what algorithm will allow me to add the additional constraints and figure out the nTH next-to-best results?
My thought is that I should be looking at Integer or Linear programming solutions? or maybe branch and bound? But I'm hoping someone can give me a bit of clarity before I get too far down the wrong path again. It should be noted that my data set will be around 500 items, so brute force is not an option.
Thank you for any help!!
You haven't posted an algorithm here so we can't show you where to change it. You have n items with positive weight $w_1,\ldots,w_n$ and positive value $v_1,\ldots,v_n$. You want to select a subset $\{i_1,\ldots,i_r\}$ of $\{1,\ldots,n\}$ such that $$\sum_{j=1}^r w_{i_j}\le W$$ and $$\sum_{j=1}^r v_{i_j}$$ as large as possible.
In the following algorithm we use tuples $(v|w|S)$ and we always have $$S \subset \{1,\ldots,n\}$$ $$\sum_{t \in S}v_t=v$$ $$\sum_{t \in S}w_t=w$$
Algorithm:
Start with the set $$M_0:=\{(0|0|\emptyset)\}$$
Then do the following step for $k=1$ to $n$: $$\begin{array}\\ M_k:=M_{k-1}\\ \text{ for all }(v|w|S) \text{ in } M_{k-1}:\\ \quad \text{ if }(v+v_k|w+w_k|S\cup\{k\}) \text{ is admissible, then: }\\ \quad \quad \text{ adjust }M_{k} \text{ by } (v+v_k|w+w_k|S\cup\{k\}) \\\end{array}$$
After $n$ steps $M_n$ was constructed. The tuple $(v|w|S) \in M_n$ with the largest $v$ gives the subset $S$ of the items that generate a maximal value.
The tuple $(v|w|S)$ is admissible if $w\le W$, which means $$\sum_{t \in S}w_t\le W$$
To adjust a set $M$ by a tuple $(v|w|S)$ means that
If you want to search some solutions different from $S_1,S_2,\ldots$ then you run the algorithm but change the definition of admissible:
The set $S$ is admissible if $$\sum_{t \in S}w_t\le W$$ and $$S\ne S_1$$ $$S\ne S_2$$
An Alternate Approach
In the previously described dynamic programming algorithm we found a tuple $(v,w,S)$ where $v$ is the maximum value we can achieve, $S$ is a subset we can use to achieve $v$ and $w$ is the sum of weights of the subset $S$.
So for each possible pair $(v|w)$ we also save a set of item indexes that is needed to get this $v$ and $w$.
If you want to find e.g. the $3$ best solutions, you can save three set of item indexes for each $(v|w)$, e.g. $(v|w|T)$, where $T=\{S_1,S_2,S_3\}$ or $T=\{S_1,S_2\}$ or $T=\{S_1\}$ or $T=\emptyset$.
If we add item $k$ to $(v|w|T)$ we get the new tuple $(v|w|\{S_1\cup\{k\},S_2\cup\{k\},S_3\cup\{k\}\})$ or $(v|w|\{S_1\cup\{k\},S_2\cup\{k\}\})$ or $(v|w|\{S_1\cup\{k\}\})$ or $(v|w|\{\{k\}\})$
We also have to adapt the step where we adjust the set $M_k$.
To adjust a set $M$ by a tuple $(v|w|S)$ means that
The expression $\text{ three from }(T\cup X)$ means a subset of three elements of $T\cup X$, if $T\cup X$ contains more than $3$ elements, or $T\cup X$ otherwise.