Summation notation problem

Question

Any help is greatly appreciated!

Outline: Hermione has been thinking about the imminent return of the Dark Lord, so she has been busy packing her bag with all the items required for her survival. Because she has so many different items, it is impossible to list them all here; however she knows that she can formulate the problem even without knowing those (trivial) details. She has $N$ items indexed from $1$ to $N$; each item $x_i$ is associated with a value $c_i$, weight $w_i$ and volume $v_i$. She cannot carry more than $W$ in weight, and the bag can only hold up to $V$ in volume. Items must either be in the backpack or not; i.e. we cannot put half a book in the bag! She needs to maximize the value of the items that she is carrying, because she knows she will not be able to replenish these for a very long time.

How would I formulate this problem using summation notation?

Answer 1

I'm not really sure what you mean with summation notation so I'm sorry when I'm answering your question wrong but you could formulate your question in 'mathematical language' as follows.

If you call $I\subset \{ 1,...,N\}$ the numbers of the items she can take. We have the following requirements about $I$: $$ \sum_{i\in I} w_i \leq W $$ $$ \sum_{i\in I} v_i \leq V $$ $$ \sum_{i\in I} c_i \mbox{ has to be maximal under the subsets } I \subset \{ 1,...,N\}$$

Answer 2

For $i=1,\ldots,N$ let $\epsilon_i=1$ if $x_i$ is in the bag, and let $\epsilon_i=0$ if $x_i$ is not in the bag. Then the total volume in the bag is

$$\sum_{k=1}^N\epsilon_iv_i\;,$$

which is just the sum of the volumes of the items in the bag: the terms corresponding to items not in the bag are $0$, because for those items $\epsilon_i=0$. Clearly we must have $$\sum_{k=1}^N\epsilon_iv_i\le V\;.$$

• Write down a similar inequality involving expressing the limitation on the total weight that she can carry.
• Write down a similar summation expressing the total value of what she carries. The problem is then to choose $\epsilon_1,\ldots,\epsilon_N$ to maximize this total value subject to the inequality constraints on volume and weight.