Summation notation

Question

Does anyone have any suggestions as to how I would be able to formulate this problem using summation notation for those of you who are familiar with it?

Hermione 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 xi 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 maximise 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.

Answer 1

So, she's looking for the subset $I\subset\{1,\ldots,N\}$ that maximizes $$\sum_{i\in I} c_i$$ while satisfying the conditions $$\sum_{i\in I} w_i\leq W$$ and $$\sum_{i\in I} v_i\leq V.$$

Answer 2

The task is to find $I\subseteq \{1,\ldots, N\}$ such that $$ \sum_{i\in I} c_i\stackrel!=\max$$ subject to the constraints $$\sum_{i\in I}w_i\le W\qquad\text{and}\qquad\sum_{i\in I}v_i\le V.$$

---

Instead of using subsets $I\subseteq \{1,\ldots,N\}$ you can also formulate the problem as loking for $\epsilon_i\in\{0,1\}$ for $i=1,\ldots, N$ such that $$ \sum_{i=1}^N \epsilon_ic_i\stackrel!=\max$$ subject to the constraints $$\sum_{i=1}^N \epsilon_iw_i\le W\qquad\text{and}\qquad\sum_{i=1}^N \epsilon_iv_i\le V.$$

Answer 3

I think you should study the greedy method Knapsack problem.It is of two types:

1. 0/1 KNAPSACK

This is what you are asking for i.e. we cant divide the items.We either keep them entirely or we dont.

2. FRACTIONAL KNAPSACK

In this we can take the fraction of an item.After reading the greedy method ,you can attempt a whole set of problems including the 1 you are asking for.Here is a list of such problem knapsack_problems_list.

So grab any good book and give it a read. :-)I know this is not the answer but it will help you more.!