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$
The proof is by induction.
To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less.
Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ..., v_n}$ with weight quantities $W = {w_1, w_2, ..., w_n}$ and a new choice $a_{n+1}$, value $v_{n+1}/w_{n+1} > v_i/w_i$ for all $i \in 1...n$ and available weight $w_{n+1}$, then a new optimal solution can be found as follows. Let $j_1$ be the index such that $v_{j_1} / w_{j_1} < v_i / w_{j_1}$ for all $i \in 1...n$ and $i \neq j_1$. If we replace $a_{j_1}$ with $a_{n+1}$, the objective function improves by $(v_{n+1} - v_{j_1}) / min(w_{n+1},w_{j_1})$. This is the largest possible increase in the objective function because any other replacement choice subtracts a larger amount than $v_{j_1} / min(w_{n+1},w_{j_1})$. We continue this replacement strategy, choosing $j_k$ as the index of the remaining item with the lowest value-to-weight ratio of the remaining items and replacing it entirely with $w_{j_k}$ of $a_i$ or with as much $a_i$ as remains. When the knapsack is completely full of $a_i$ or all available $a_i$ has been placed in the knapsack, we have an optimal solution, achieved by being as greedy as possible with the choice $a_i$.
QED
Best Answer
I think this should work:
Maximize: $$\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij}$$ Subject to: $$ \begin{align} \sum _{i=1}^{n}\sum _{j=1}^{\left | G_{i} \right |}w_{ij}x_{ij} &\leq c \\ \sum _{j=1}^{\left | G_{i} \right |}x_{ij} &= 1 \\ \sum _{j=1}^{\left | G_{s} \right |}x_{sj} &= 3 \\ x_{ij} \in \{0,1\} \end{align} $$ Notation:
N the number of items
n the number of groups
c the capacity of a single knapsack
G = {$G_{1},...,G_{n}$} the set of groups
${\left | G_{i} \right |}$ the number of items in group $G_{i}$
${\left | G_{s} \right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$