0/1 knapsack upper bound I'm new to the 0/1 knapsack problem and I've ordered my nodes into profit/weight as:
Knapsack max weight: 12
i     Weight     Profit     Profit/Weight
1      4           30          7.5
2      6           42           7
3      6           36           6
4      4           8            2

Calculating the upper bound:
Going off of the lecturers slides for a similiar example, the upper bound is then calculated by adding the items at the top of this list to the knapsack, this leaves us with only items 1 and 2 and a space left over with a total of 72 profit. 
Clearly items number 2 and 3 also fit into the max weight and create a higher upper bound. Is there something I'm supposed to do to avoid this or do I continue with the process?
 A: The IP is:
$$\max \Pi = 30x_1 + 42x_2 + 36x_3+ 8x_4$$ $$s.t.$$ $$4x_1 +6x_2 + 6x_3 +4x_4≤12$$
$$x_i \in \text{{$0,1$}}$$
What you did gives a lower bound of $72$ on the max. In order to find an upper bound, RELAX the integrality constraint of $x_i \in \text{{$0,1$}}\to x_i\in [0,1]$
Now, it is clear that we can use a greedy strategy for this:
solution: $x_1=1, x_2=1, x_3=\frac 13 \Rightarrow \Pi_{ub} = 84$
Thus, $72≤\Pi^*≤84$
Now, we use branch and bound...
Build a tree
Condition on the value of $x_3$, solve the program twice using our greedy strategy  fixing $x_3=1$ and forcing $x_3=0$.
$x_3=1$
$\Rightarrow solution\text{ }x_3=1,x_1=1, x_2=\frac 13 \Rightarrow \Pi=80$
$x_3=0$
$\Rightarrow solution\text{ }x_3=0,x_1=1, x_2=1, x_4= \frac 12 \Rightarrow \Pi=76$
Now, pick a side of the tree to branch again on.
choose $x_3=1$ now, there are two possibilities $x_2=0, x_2=1$
Now, we fix $x_3=1, x_2=1 \Rightarrow \text{ solution }x_3=1, x_2=1 \Rightarrow \Pi = 78 = \Pi_{candidate}$ This is a candidate solution because it is integral
Now, we need to show that the previous solution is optimal.
choose  $x_3=1, x_2=0  \Rightarrow \text{ solution }x_3=1, x_2=0, x_1=1, x_4=\frac 12 \Rightarrow \Pi = 70$ So, we can prune this branch of the tree since $70<\Pi_{candidate}$
Look at the other side of the tree with $x_3=0$ fixed
We have two possibilities: $x_4=0, x_4=1$
$x_3=0, x_4=0 \Rightarrow \text{ solution }x_1=1, x_2=1 \Rightarrow \Pi = 72 < \Pi_{candidate}$ again, we prune this branch since our candidate solution is better.
$x_3=0, x_4=1 \Rightarrow \text{ solution }x_1=1, x_2=\frac 23, x_4=1 \Rightarrow \Pi = 66 < \Pi_{candidate}$ again, we prune this branch since our candidate solution is better, and we're done since the tree has no more branches.
Hence, $\Pi^* = 78 \text{ with }x_1=0, x_2=1, x_3=1, x_4=0$
A: $$\begin{array}{ll} \text{maximize} & 30 x_1 + 42 x_2 + 36 x_3+ 8 x_4\\ \text{subject to} & 4 x_1 + 6x_2 + 6 x_3 + 4x_4 \leq 12\\ & x_i \in \{0,1
\}\end{array}$$
The search space is so small that we can simply use brute force. In Haskell,
λ map (\(x1,x2,x3,x4)->((x1,x2,x3,x4),30*x1+42*x2+36*x3+8*x4)) $ filter (\(x1,x2,x3,x4)->4*x1+6*x2+6*x3+4*x4<=12) [ (x1,x2,x3,x4) | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1], x4 <- [0,1] ]
[((0,0,0,0),0),((0,0,0,1),8),((0,0,1,0),36),((0,0,1,1),44),((0,1,0,0),42),((0,1,0,1),50),((0,1,1,0),78),((1,0,0,0),30),((1,0,0,1),38),((1,0,1,0),66),((1,1,0,0),72)]

Hence, the maximum is $78$, which is attained at $(x_1, x_2, x_3, x_4) = (0,1,1,0)$.
