0
$\begingroup$

I'm trying to solve following modified knapsack problem using dynamic programming.

What we know:

  • Total number of items
  • Item weight, value and type
  • Knapsack capacity

Aims

  • Find Maximum weight of knapsack
  • List taken Items

Constraints

  • Only one item of each type can be taken

For example, in my problem, the item list would look like:

Fruit

Banana (weight 9, value 10)
Apple (weight 4, value 30)
...

Vegetable

Potato (weight 2, value 20)
Onion (weight 3, value 25)
...

Sweet

Chocolate(weight 4, value 30)
Cookie(weight 2, value 30)
...

and so on, where the problem requires that you select exactly one item from Fruit, one item from Vegetable, one item from Sweet, and so on.

Can anyone give me some advice about algorithm or pseudo code?

$\endgroup$
2
  • $\begingroup$ Please credit the source of the problem, such as providing a url or the name of a book or the name of your instructor. $\endgroup$
    – John L.
    May 7 at 16:28
  • $\begingroup$ It looks like the "value" of an item is irrelevant. Is it? $\endgroup$
    – John L.
    May 7 at 16:30

1 Answer 1

1
$\begingroup$

Let $C \ge 1$ be the capacity of the knapsack and let $G_1, \dots,G_k$ be your groups, where each group is a non-empty collection of items, i.e., $G_i = \{ x^{(i)}_1, x^{(i)}_2, \dots \}$. Groups are pairwise disjoint. Define $n= \sum_{i=1}^k |G_i|$ as the total number of items in the instance.

For any item $x$, let $w(x)$ and $v(x)$ denote its weight and value, respectively, and assume for simplicity that the all weights and the values of the above items positive. It is helpful to imagine the existence of $k$ additional items $x_1^{(0)}, \dots, x_k^{(0)}$, each with value and weight $0$.

Here are three possible algorithms. Pick the fastest one according to your instance.


For $i=0, \dots, k$ and $c=0, \dots, C$, define $OPT[i, c]$ as the maximum overall value that can be obtained by selecting at most one element from each of the group $G_1, \dots, G_i$ and no elements from the groups $G_{i+1}, \dots, G_k$, with the constraint that the total weight of the selected elements must be at most $c$.

According the above definition we have $OPT[0,c] = 0$ and, for $i > 0$ $$ OPT[i,c] = \max_{\substack{j=0, \dots, |G_i| \\ w(x^{(i)}_j) \le c}} \left( v(x^{(i)}_j) + OPT\left[i-1, c-w(x^{(i)}_j)\right] \right). $$

You can compute all the quantities $OPT[i,c]$ in non-decreasing order of $i$. Since $OPT[i,c]$ can be fond in time $O(|G_i|)$, the overall time complexity is $$ O\left( C \cdot \sum_{i=1}^k |G_i| \right) = O(C \cdot n). $$

The value of the optimal solution is $OPT[k, C]$ and an optimal set of items to select can be found using standard techniques.


Let $V$ be an upper bound on the maximum attainable value. For example: $V = \sum_{i=1}^k \max G_i$.

For $i=0, \dots, k$ and $v=0, \dots, V$, define $OPT[i, v]$ as the minimum overall weight of a set of items that has an overall value of at least $v$ and can be obtained by selecting at most one element from each of the group $G_1, \dots, G_i$ and no elements from the groups $G_{i+1}, \dots, G_k$. If no such set of items exists, define $OPT[i, v]= +\infty$.

We have $OPT[0, 0] = 0$, and $OPT[0, v] = +\infty$ for $v>0$. Moreover, for $i>0$: $$ OPT[i, v] = \min_{j=0,\dots,|G_i| } \left( w(x^{(i)}_j) + OPT\left[i-1, \max\{v - v(x^{(i)}_j), 0 \}\right] \right). $$

The value of the optimal solution is $\max \{v \mid v=0, \dots, V \wedge OPT[k, v] \le C\}$. Again, you can solve all subproblems in non-decreasing order of $i$, where each $OPT[i, v]$ can be found in time $O(|G_i|)$ yielding an overall time complexity of $O(V \cdot n)$.


Partition the groups into three sets $\mathcal{G}_1, \mathcal{G}_2, \mathcal{G}_3$ such that $\sum_{G_i \in \mathcal{G}_1} |G_i| \le n/2$, $\sum_{G_i \in \mathcal{G}_2} |G_i| \le n/2$, and $|\mathcal{G}_3| = 1$.

Guess an element $x^*$ that belongs to the only group in $\mathcal{G}_3$. There are at most $O(n)$ choices.

Exhaustively generate all sets that can be constructed by selecting at most one element from each group in $\mathcal{G}_1$ (and no elements from other groups). For each such set $S$ look at the pair $(\sum_{x \in S} w(x), \sum_{x \in S} v(x))$ and collect all these pairs into a list $L_1$. Notice how there are at most $O(2^{n/2})$ sets to examine, which means that we can build $L_1$ in time $O(n \cdot 2^{n/2})$.

Repeat the same procedure for $\mathcal{G}_2$ to obtain a list $L_2$. Sort the pairs $(w,v)$ in $L_2$ in non-decreasing order of $w$ and use this sorted list to compute a value $\nu(w)$ for each $w$ that appears in some pair $(w, v)$ in $L_2$. Specifically, $\nu(w) = \max_{\substack{(w',v') \in L_2 \\ w' \le w}} v'$, i.e., $\nu(w)$ is the maximum value that can be obtained by selecting at most one item from each set in $\mathcal{G}_2$ without exceeding an overall weight of $w$. Sorting $L_2$ requires time $O(n \cdot 2^{n/2})$, while the quantities $\nu(w)$ can be found by a linear scan of (the sorted version) of $L_2$.

Finally, for each pair $(w, v)$ in $L_1$ with $C-w-w(x^*) \ge 0$, we can fetch $\nu(C-w-w(x^*))$ in time $O(\log |L_2|) = O(\log 2^{n/2}) = O(n)$ and consider the quantity $v + v(x^*) + \nu(v)$ as a candidate answer.

The maximum among all candidate answers is the value of an optimal solutions to your original instance. The overall time spent is $O(n^2 \cdot 2^{n/2})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.